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

本题属于比较简单的最短路问题

注：若无向图出现相同边但权值不同要特别判断

#include
   
    #include
    
     #define inf 1e8 + 10bool vis[1005];int dis[1005],w[1005];int a[1005][1005],b[1005][1005];int n,m;void Dijkstra(int s,int t){    memset(vis,false,sizeof(vis));    for(int i=1; i<=n; i++)    {        dis[i] = a[s][i];        w[i] = b[s][i];    }    vis[s] = true;    for(int i=1; i<=n; i++)    {        int r,q = inf;        for(int j=1; j<=n; j++ )        {            if(!vis[j]&&dis[j]
     
      dis[r]+a[r][j])            {                dis[j] = dis[r] + a[r][j] ;                w[j] = w[r] + b[r][j] ;            }            if(dis[j]==dis[r]+a[r][j])            {                if(w[j]>w[r] + b[r][j])                {                    w[j] = w[r] + b[r][j];                }            }        }    }    printf("%d %d\n",dis[t],w[t]);}int main(){    int x,y,d,p,s,t;    while(scanf("%d%d",&n,&m),n+m)    {        memset(a,126,sizeof(a));        memset(b,126,sizeof(b));        for(int i=0; i
      
       d)//判断出现相同边路费不同不同            {                a[x][y]=a[y][x]=d;                b[x][y]=b[y][x]=p;            }            else if(a[x][y]==d)            {                if(b[x][y]>p)                    b[x][y]=b[y][x]=p;            }        }        scanf("%d%d",&s,&t);        Dijkstra(s,t);    }}
      
     
    
   

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