poj 2449 k短路模板

[cpp]
#include <iostream> 
#include <stdio.h> 
#include <cstring> 
#include <queue> 
#include <algorithm> 
using namespace std; 
const int maxn=1001; 
const int maxm=100001; 
const int inf=1<<30; 
struct edge 
{ 
    int from,to,next,w; 
}; 
edge e1[maxm]; 
edge e2[maxm]; 
int head1[maxn]; 
int head2[maxn]; 
int dist[maxn]; 
bool vis[maxn]; 
struct node//存储搜索过程中点的信息 
{ 
    int to; 
    int g,f;//f=g+h 
    bool operator <(const node &r) const 
    { 
        if(r.f==f) return r.g<g; 
        else return r.f<f; 
    } 
}; 
int n,m,t1,t2,k,cnt,s,end;//第k短路 
void add1(int i,int j,int w) 
{ 
    e1[t1].from=i; 
    e1[t1].to=j; 
    e1[t1].w=w; 
    e1[t1].next=head1[i]; 
    head1[i]=t1++; 
} 
void add2(int i,int j,int w) 
{ 
    e2[t2].from=i; 
    e2[t2].to=j; 
    e2[t2].w=w; 
    e2[t2].next=head2[i]; 
    head2[i]=t2++; 
} 
void spfa(int s)//求出路径当前值到终点的最短距离 
{ 
    queue <int> q; 
    q.push(s); 
    for(int i=1;i<=n;i++) dist[i]=inf; 
    memset(vis,false,sizeof(vis)); 
    dist[s]=0;     
    while(!q.empty()) 
    { 
        int u=q.front(); 
        q.pop(); 
        vis[u]=false;//用vis来标记点是否在队列中 
        for(int i=head2[u];i!=-1;i=e2[i].next) 
        { 
            int v=e2[i].to; 
            if(dist[v]>dist[u]+e2[i].w) 
            { 
                dist[v]=dist[u]+e2[i].w; 
                if(!vis[v]) 
                { 
                    q.push(v); 
                    vis[v]=true; 
                } 
            } 
        } 
    } 
} 
int A(int s,int end,int k) 
{ 
    int cnt=0; 
    node e,ne; 
    priority_queue <node> que;     
    if(s==end) k++;//特判 
    if(dist[s]==inf) return -1; 
    e.to=s;     
    e.f=e.g+dist[e.to];//估价函数的公式 
    que.push(e); 
    while(!que.empty()) 
    { 
        e=que.top(); 
        que.pop(); 
        if(e.to==end) cnt++;//统计终点出队的次数 
        if(cnt==k) return e.g;//计算t出队的次数，如果t出对的次数=k，则当前的路径长度g记为第k短路 
        for(int i=head1[e.to];i!=-1;i=e1[i].next) 
        { 
            ne.to=e1[i].to; 
            ne.g=e.g+e1[i].w; 
            ne.f=ne.g+dist[ne.to]; 
            que.push(ne); 
        } 
    } 
    return -1; 
} 
int main() 
{ 
    int u,v,w; 
    while(scanf("%d%d",&n,&m)==2) 
    { 
        memset(head1,-1,sizeof(head1)); 
        memset(head2,-1,sizeof(head2)); 
        memset(e1,0,sizeof(e1)); 
        memset(e2,0,sizeof(e2)); 
        t1=t2=0; 
        for(int i=1;i<=m;i++) 
        { 
            scanf("%d%d%d",&u,&v,&w); 
            add1(u,v,w); 
            add2(v,u,w); 
        } 
        scanf("%d%d%d",&s,&end,&k); 
        spfa(end); 
        int ans=A(s,end,k); 
        printf("%d\n",ans); 
    } 
    return 0; 
} 

补充：软件开发 , C++ ,