hdu1385 Minimum Transport Cost

 1 #include<stdio.h>
 2 #define Max 0xfffffff
 3 #define N 600
 4 bool vis[N];
 5 int path[N][N];//昨天把path数组定义为BOOl型了，输出的时候老是死循环，昨天检查了一晚上没发现，今天多亏了我强悍的队友给我指明了错误！！ 
 6 int d[N][N],cost[N];
 7 int vexnum,arcnum;
 8 void floyd()
 9 {
10     for(int k=0;k<vexnum;++k)
11         for(int i=0;i<vexnum;++i)
12             for(int j=0;j<vexnum;++j){
13                 int temp=d[i][k]+d[k][j]+cost[k];
14                 if(d[i][j]>temp||(d[i][j]==temp&&path[i][k]<path[i][j])){
15                     d[i][j]=temp;
16                     path[i][j]=path[i][k];
17                 }
18             }
19 }
20 int main()
21 {
22     int i,j,k,start,end;
23     while(scanf("%d",&vexnum),vexnum){
24         for(i=0;i<vexnum;++i){
25             for(j=0;j<vexnum;++j){
26                 scanf("%d",&d[i][j]);
27                 if(d[i][j]==-1)
28                     d[i][j]=d[j][i]=Max;
29                 path[i][j]=j;
30             }
31         }
32         for(i=0;i<vexnum;++i)
33             scanf("%d",&cost[i]);
34         floyd();
35         while(scanf("%d%d",&start,&end),~start||~end){
36             printf("From %d to %d :\nPath: %d",start,end,start);
37             start--;end--;
38             int k=start;
39             while(k!=end){
40                 printf("-->%d",path[k][end]+1);
41                 k=path[k][end];
42             }
43             printf("\nTotal cost : %d\n\n",d[start][end]);
44         }
45     }
46     return 0;
47 }