Floyd算法——保存路径——输出路径 HDU1385

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1385

参考 http://blog.csdn.net/shuangde800/article/details/8075165

题目大意：

有N个城市，然后直接给出这些城市之间的邻接矩阵，矩阵中-1代表那两个城市无道路相连，其他值代表路径长度。

如果一辆汽车经过某个城市，必须要交一定的钱(可能是过路费)。

现在要从a城到b城，花费为路径长度之和，再加上除起点与终点外所有城市的过路费之和。

求最小花费，如果有多条路经符合，则输出字典序最小的路径。

解析：

直接跑一边Floyd算法就好用一个二维数组保存路径path[ i ][ j ]表示第i个节点到第j个节点经过的第一个点（例如1->2->5->4，path[1][4]=2,path[2][4]=5,path[5][4]=5）

AC代码

 #include <stdio.h>

 #include <math.h>

 #include <string.h>

 #include <stdlib.h>

 #include <iostream>

 #include <sstream>

 #include <algorithm>

 #include <string>

 #include <queue>

 #include <map>

 #include <vector>

 using namespace std;

 const int maxn = ;

 const int maxm = 1e4+;

 const int inf = 0x3f3f3f3f;

 const double epx = 1e-;

 typedef long long ll;

 int n;

 int w[maxn][maxn];

 int path[maxn][maxn];

 int tax[maxn];

 void init()

 {

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

     {

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

         {

             if(i!=j)

                 w[i][j]=inf;

             else

                 w[i][j]=;     //自己到自己设为0

             path[i][j]=j;　　　　//初始化为j

         }

     }

 }

 void Floyd()

 {

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

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

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

         if(w[i][k]!=inf&&w[k][j]!=inf)

         {

             int temp=w[i][k]+w[k][j]+tax[k];    //tax[]是过路费

             if(w[i][j]>temp)                   //松弛操作的时候，顺带更新路径

             {

                 w[i][j]=temp;

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

             }

             else if(w[i][j]==temp&&path[i][j]>path[i][k])//字典序最小，不要求字典序的话可直接省略

             {

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

             }

         }

 }

 int main()

 {

     while(cin>>n&&n)

     {

         init();

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

         {

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

             {

                 cin>>w[i][j];

                 if(w[i][j]==-)

                     w[i][j]=inf;

             }

         }

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

             cin>>tax[i];

         Floyd();

         int s,e;

         while(cin>>s>>e&&s!=-&&e!=-)

         {

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

             printf("Path: ");

             int u=s;

             printf("%d",u);                 //打印路径

             while(u!=e)

             {

                 printf("-->%d",path[u][e]);

                 u=path[u][e];

             }

             printf("\n");

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

         }

     }

 }

巴特西

Floyd算法——保存路径——输出路径 HDU1385

最新文章

热门文章