本文共 3799 字，大约阅读时间需要 12 分钟。

#include
   
    using namespace std;const int maxn=507;const int maxm=300007;int n,m;int s,e;int cnt,head[maxn];int vis[maxn],dis[maxn],span[maxn],pred[maxn],pret[maxn],step[maxn];int ans1[maxn],ans2[maxn],cnt1,cnt2;struct node{
       int to;    int next;    int cost;    int time;}edge[maxm];void add(int x,int y,int z,int t){
       edge[++cnt].to=y;    edge[cnt].next=head[x];    edge[cnt].cost=z;    edge[cnt].time=t;    head[x]=cnt;}void dij(int start){
       memset(dis,0x3f,sizeof(dis));    memset(span,0x3f,sizeof(span));    memset(step,0x3f,sizeof(step));    vis[start]=1;    dis[start]=0;    span[start]=0;    step[start]=0;    for(int i=head[start];i;i=edge[i].next)    {
           int v=edge[i].to;        if(dis[v]>dis[start]+edge[i].cost||(dis[v]==dis[start]+edge[i].cost&&step[v]>step[start]+1))        {
               step[v]=step[start]+1;            dis[v]=dis[start]+edge[i].cost;            pred[v]=start;        }        if(span[v]>span[start]+edge[i].time||(span[v]==span[start]+edge[i].time&&dis[v]>dis[start]+edge[i].cost))        {
               span[v]=span[start]+edge[i].time;            pret[v]=start;        }    }  /*  queue
    
     q;    q.push(start);    step[start]=0;    while(!q.empty())    {        int u=q.front();        q.pop();        vis[u]=0;        for(int i=head[u];i;i=edge[i].next)        {            int v=edge[i].to;            if(dis[v]>dis[u]+edge[i].cost||(dis[v]==dis[u]+edge[i].cost&&step[v]>step[u]+1))            {                step[v]=step[u]+1;                dis[v]=dis[u]+edge[i].cost;                pred[v]=u;                if(!vis[v])                {                    q.push(v);                    vis[v]=1;                }            }        }    }*/    while(1)    {
           int mi=10000000,flag=-1;        for(int i=1;i<=n;i++)        {
               if(dis[i]
     
      dis[flag]+edge[i].cost||(dis[v]==dis[flag]+edge[i].cost&&step[v]>step[flag]+1))            {
                   step[v]=step[flag]+1;                dis[v]=dis[flag]+edge[i].cost;                pred[v]=flag;            }        }    }    memset(vis,0,sizeof(vis));    vis[start]=1;    while(1)    {
           int mi=10000000,flag=-1;        for(int i=1;i<=n;i++)        {
               if(span[i]
      
       span[flag]+edge[i].time||(span[v]==span[flag]+edge[i].time&&dis[v]>dis[flag]+edge[i].cost))            {
                   span[v]=span[flag]+edge[i].time;                pret[v]=flag;            }        }    }}void print(int cur){
       if(cur==0) return ;    print(pret[cur]);    ans1[++cnt1]=cur;    //printf("%d => ",cur);}void prind(int cur){
       if(cur==0) return;    prind(pred[cur]);    ans2[++cnt2]=cur;    //printf("%d => ",cur);}int main(){
       int a,b,c,d,e;    scanf("%d%d",&n,&m);    while(m--)    {
           cin>>a>>b>>c>>d>>e;        add(a,b,d,e);        if(c==0)        add(b,a,d,e);    }    cin>>s>>e;    dij(s);    //printf("Time = %d: ",span[e]);    print(pret[e]);    //printf("%d\n",e);    //printf("Distance = %d: ",dis[e]);    prind(pred[e]);    //printf("%d\n",e);    int flag=0;    if(cnt1==cnt2)    {
           int i;        for(i=1;i<=cnt1;i++)        {
               if(ans1[i]!=ans2[i])            {
                   break;            }        }        if(i==cnt1+1) flag=1;    }    if(flag==1)    {
           printf("Time = %d; Distance = %d: ",span[e],dis[e]);        for(int i=1;i<=cnt1;i++)        printf("%d => ",ans1[i]);        printf("%d\n",e);    }    else    {
           printf("Time = %d: ",span[e]);        for(int i=1;i<=cnt1;i++)        printf("%d => ",ans1[i]);        printf("%d\n",e);        printf("Distance = %d: ",dis[e]);        for(int i=1;i<=cnt2;i++)        printf("%d => ",ans2[i]);        printf("%d\n",e);    }    return 0;}
      
     
    
   

转载地址：http://lsgwi.baihongyu.com/