hdu1385 Minimum Transport Cost

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 #define M 100
 6 #define inf 0xffffff
 7 int map[M][M];
 8 int dis[M][M],n,b[M];
 9 int main()
10 {
11     int i,j;
12     void floyd();
13     while(cin>>n,n)
14     {
15         for(i=1; i<=n; i++)
16             for(j=1; j<=n; j++)
17             {
18                 cin>>map[i][j];
19                 if(map[i][j]==-1)
20                     map[i][j]=inf;
21             }
22         for(i=1; i<=n; i++)
23             cin>>b[i];
24         floyd();
25         int x,y;
26         while(cin>>x>>y,x!=-1)
27         {
28             printf("From %d to %d :\nPath: ",x,y);
29             int next=x;
30             while(next!=y)
31             {
32                 printf("%d-->",next);
33                 next=dis[next][y];
34             }
35             printf("%d\nTotal cost : %d\n\n",y,map[x][y]);
36         }
37     }
38     return 0;
39 }
40 void floyd()
41 {
42     int i,j,k;
43     for(i=1; i<=n; i++)
44         for(j=1; j<=n; j++)
45             dis[i][j]=j;
46     for(k=1; k<=n; k++)
47         for(i=1; i<=n; i++)
48         {
49             if(map[i][k]!=inf)
50                 for(j=1; j<=n; j++)
51                 {
52                     int _next=map[i][k]+map[k][j]+b[k];
53                     if(map[i][j]>_next)
54                     {
55                         map[i][j]=_next;
56                         dis[i][j]=dis[i][k];
57                     }
58                     else if(map[i][j]==_next) dis[i][j]=min(dis[i][j],dis[i][k]);
59                 }
60         }
61 }