Problem Description
给你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时输入结束。
(1<n<=1000, 0<m<100000, s != t)
Output
输出 一行有两个数， 最短距离及其花费。
Sample Input
3 2 1 2 5 6 2 3 4 5 1 3 0 0
Sample Output
9 11
思路：dijk算法就Ok。
坑点：
1.边输入时有可能后输入的更长的重复路，所以要判断一下覆盖。
2.路长相等的情况下，需要判断一下谁的花费少。
1 #include<cstdio> 2 #include<cstring> 3 #define Inf 0x3f3f3f3f 4 using namespace std; 5 int n,m,s,t,sum; 6 int G[1005][1005],mark[1005],dis[1005],fee[1005][1005],f[1005]; 7 8 void Getmap(){ 9 int a,b,d,p; 10 memset(G,Inf,sizeof(G)); 11 memset(fee,Inf,sizeof(fee)); 12 for(int i=1;i<=n;i++){ 13 G[i][i]=0; 14 fee[i][i]=0; 15 } 16 for(int i=0;i<m;i++){ 17 scanf("%d%d%d%d",&a,&b,&d,&p); 18 if(G[a][b]>d){//覆盖 19 G[a][b]=G[b][a]=d; 20 fee[a][b]=fee[b][a]=p; 21 } 22 } 23 } 24 25 void Dijk(){ 26 int mini,p=s; 27 memset(mark,0,sizeof(mark)); 28 for(int i=1;i<=n;i++){ 29 dis[i]=G[s][i]; 30 f[i]=fee[s][i]; 31 } 32 33 for(int k=1;k<n;k++){ 34 mini=Inf; 35 for(int i=1;i<=n;i++) 36 if(!mark[i]&&dis[i]<mini){ 37 mini=dis[i]; 38 p=i; 39 } 40 mark[p]=1; 41 42 for(int i=1;i<=n;i++) 43 if(dis[i]>dis[p]+G[p][i]){ 44 dis[i]=dis[p]+G[p][i]; 45 f[i]=f[p]+fee[p][i]; 46 } 47 else if(dis[i]==dis[p]+G[p][i]&&f[i]>f[p]+fee[p][i]){//路长度相等，判断一下哪个路花费少 48 f[i]=f[p]+fee[p][i]; 49 } 50 } 51 } 52 53 int main(){ 54 while(scanf("%d%d",&n,&m)){ 55 if(n==0&&m==0) break; 56 Getmap(); 57 scanf("%d%d",&s,&t); 58 Dijk(); 59 printf("%d %d ",dis[t],f[t]); 60 } 61 return 0; 62 }