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

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

Input

输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。 

Output

输出 一行有两个数， 最短距离及其花费。

Sample Input

3 21 2 5 62 3 4 51 30 0

Sample Output

9 11

 C++版本一

Floyed-Warshall算法

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;#define INF 0x3f3f3f3fint n,m,s,t;int a,b,d,p;int map[1010][1010];int money[1010][1010];int main(){    while(~scanf("%d%d",&n,&m)){        if(n==0&&m==0)  break;        for(int i=1; i<=n; i++)            for(int j=1;j<=n;j++)                if(i==j) map[i][j]=0;                else map[i][j]=INF;        for(int i=1;i<=m;i++){            scanf("%d%d%d%d",&a,&b,&d,&p);            map[a][b]=d;            money[a][b]=p;        }        scanf("%d%d",&s,&t);        for(int k=1; k<=n; k++)            for(int i=1; i<=n; i++)                for(int j=1; j<=n; j++)                {                    if(map[i][j]>map[i][k]+map[k][j]){                        map[i][j]=map[i][k]+map[k][j];                        money[i][j]=money[i][k]+money[k][j];                    }                }        cout << map[s][t] << " " << money[s][t] << endl;    }    //cout << "Hello world!" << endl;    return 0;}
       
      
     
    
   

C++版本二

#include
   
    using namespace std;struct node{    int e;    int w;    int cost;};struct cmp{    bool operator()(const node &a,const node &b)    {        if(a.w!=b.w)            return a.w>b.w;        else            return a.cost>b.cost;    }};int main(){    int n,m,s,t;    while(scanf("%d%d",&n,&m)==2&&(n||m))    {        priority_queue
    
     
      ,cmp>que;        vector
      
       v[1001];        int vis[1001]={0};        node x;        while(m--)        {            int a,b,d,p;            scanf("%d %d %d %d",&a,&b,&d,&p);            x.e=b,x.w=d,x.cost=p;            v[a].push_back(x);            x.e=a;            v[b].push_back(x);        }        scanf("%d%d",&s,&t);        x.e=s,x.w=0,x.cost=0;        que.push(x);        while(!que.empty())        {            x=que.top();            que.pop();            vis[x.e]=1;            if(x.e==t)                break;            for(int i=0,j=v[x.e].size(); i
      
     
    
   

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