ZOJ 1456 Minimum Transport Cost（floyd+后继路径记录）

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1456

题意：
求最短路并且输出字典序最小的答案。

思路：
如果用dijkstra来做的话，会比较麻烦，这里直接用floyd会简单的多，只需要记录好后继路径即可。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn =  + ;

 int n, m;

 int val[maxn];

 int mp[maxn][maxn];

 int path[maxn][maxn];

 void floyd()

 {

     for(int k=;k<=n;k++)

     {

         for(int i=;i<=n;i++)

         {

             for(int j=;j<=n;j++)

             {

                 if(mp[i][k]==INF || mp[k][j]==INF)  continue;

                 int sum=mp[i][k]+mp[k][j]+val[k];

                 if(mp[i][j]>sum)

                 {

                     mp[i][j]=sum;

                     path[i][j]=path[i][k];

                 }

                 else if(mp[i][j]==sum && path[i][j]>path[i][k])

                     path[i][j]=path[i][k];

             }

         }

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     while(~scanf("%d",&n) && n)

     {

         for(int i=;i<=n;i++)

         for(int j=;j<=n;j++)

         {

             scanf("%d",&mp[i][j]);

             if(mp[i][j]==-)   mp[i][j]=INF;

             path[i][j]=j;  //i的后继路径为j

         }

         for(int i=;i<=n;i++)  scanf("%d",&val[i]);

         floyd();

         while(true)

         {

             int s,t;

             scanf("%d%d",&s,&t);

             if(s==- && t==-)  break;

             printf("From %d to %d :\n",s,t);

             printf("Path: %d",s);

             int tmp=s;

             while(tmp!=t)

             {

                 printf("-->%d",path[tmp][t]);

                 tmp=path[tmp][t];

             }

             printf("\n");

             printf("Total cost : %d\n\n",mp[s][t]);

         }

     }

     return ;

 }