HDU 1385 Minimum Transport Cost：最短路，打印字典序路径

HDU 1385 Minimum Transport Cost：最短路，打印字典序路径2014-12-02链接：

http://acm.hdu.edu.cn/showproblem.php？pid=1385

题目大意：

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

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

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

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

分析与总结：

1. 这题的关键在于按照字典序输出路径。

假设有

1--->2 2

2--->3 1

1--->3 3

求1到3的最小花费路径.

那么显然后两条路:

1-->3 3

1-->2-->3 3

它们的花费是相同的，但是路径的字典序不同，“123”比“13”字典序要小，所以应当输出1-->2-->3.

2. 用一个数组pre记录每一点的上一个结点。按照一般的单源最短路算法，在松弛时是有“小于”就直接松弛，而这题还要判断“等于”的情况，在“等于”之时，这是要选择哪一个父结点所形成的路径字典序较小，就选择哪一个父结点。

所以，在“等于”之时，可以求出原先的路径，再求出当前这个的路径，把路径转化成字符串，然后直接比较大小决定是否要换父结点。

3. 求路径的方法并转化为字符串的方法，其实很简单，用一个3行的递归函数就解决了。

4. 本题学到的新东西：

之后在网上搜题解，发现还可以用Floyd算法来解决，很神奇，再次感叹Floyd算法的强大，自己也只理解了个皮毛。

代码：

1. SPFA

#include<iostream>#include<cstdio>#include<cstring>#include<queue>using namespace std;const int INF = 0x7fffffff;const int VN= 105;int n;int w[VN][VN];int charge[VN];int d[VN];int pre[VN];bool inq[VN];int pos=0;void init（）{for（int i=0; i<=n; ++i）{w[i][i] = INF;for（int j=i+1; j<=n; ++j）w[i][j]=w[j][i]=INF;}}// 获得从开始点到当前点的路径，转化成字符串void dfs（int u, char *str）{if（u==-1）return;dfs（pre[u],str）;str[pos++] = u+"0";}bool cmp（int origin, int now）{char str1[100], str2[100];//1. 获取原来的路径pos=0;dfs（origin,str1）;str1[pos] = "";//2.获取当前点的路径pos=0;dfs（now, str2）;str2[pos++] = origin+"0"; str2[pos] = "";//3.比较是否比原来的字典序小if（strcmp（str1, str2）==1）return true;return false;}void SPFA（int src）{memset（inq, 0, sizeof（inq））;memset（pre, -1, sizeof（pre））;int i,j;for（i=1; i<=n; ++i） d[i]=INF;d[src] = 0;queue<int>q;q.push（src）;while（！q.empty（））{int u = q.front（）; q.pop（）;inq[u] = false;for（int v=1; v<=n; ++v）if（w[u][v]！=INF）{int tmp = d[u]+w[u][v]+charge[v];if（d[v] > tmp）{d[v] = tmp;pre[v] = u;if（！inq[v]）{inq[v] = true;q.push（v）;}}else if（d[v] == tmp && cmp（v, u））{pre[v] = u; }} }}// 打印路径void print_path（int u）{if（pre[u]==-1）{printf（"%d",u）;return;}print_path（pre[u]）;printf（"-->%d",u）;}int main（）{ int i,j,src,des;while（scanf（"%d",&n）,n）{init（）;for（i=1; i<=n; ++i）{for（j=1; j<=n; ++j）{scanf（"%d",&w[i][j]）;if（w[i][j]==-1） w[i][j]=INF;}}for（i=1; i<=n; ++i）scanf（"%d",&charge[i]）;while（scanf（"%d%d",&src,&des））{if（src==-1&&des==-1） break;// 备份int tmp1=charge[src], tmp2=charge[des];charge[src]=0, charge[des]=0; // 起始点和终点Tax收费为0SPFA（src）;printf（"From %d to %d :
",src,des）;printf（"Path: "）;print_path（des）;printf（"
Total cost : %d

", d[des]）;// 恢复charge[src]=tmp1, charge[des]=tmp2;}}return 0;}

2. Floyd 记录路径

#include<iostream>#include<cstdio>#include<cstring>#include<queue>using namespace std;const int INF = 0x7fffffff;const int VN= 105;int n;int w[VN][VN];int path[VN][VN];int charge[VN];void init（）{for（int i=0; i<=n; ++i）{for（int j=0; j<=n; ++j）{if（i！=j）w[i][j]=INF;else w[i][j]=0;path[i][j] = j;// path[i][j]表示点i到j经过的第一个点`}}}void Floyd（）{for（int k=1; k<=n; ++k）for（int i=1; i<=n; ++i）for（int j=1; j<=n; ++j）if（w[i][k]！=INF && w[k][j]！=INF）{int tmp = w[i][k]+w[k][j]+charge[k];if（w[i][j] > tmp）{w[i][j] = tmp;path[i][j] = path[i][k];}else if（w[i][j] == tmp && path[i][j]>path[i][k]）{path[i][j] = path[i][k];}}} int main（）{ int i,j,src,des;while（scanf（"%d",&n）,n）{init（）;for（i=1; i<=n; ++i）{for（j=1; j<=n; ++j）{scanf（"%d",&w[i][j]）;if（w[i][j]==-1） w[i][j]=INF;}}for（i=1; i<=n; ++i）scanf（"%d",&charge[i]）;Floyd（）;while（scanf（"%d%d",&src,&des））{if（src==-1&&des==-1） break;printf（"From %d to %d :
",src,des）;printf（"Path: "）;int u = src;printf（"%d",u）;while（u ！= des）{printf（"-->%d",path[u][des]）;u = path[u][des];}puts（""）;printf（"Total cost : %d

", w[src][des]）;}}return 0;}

作者：csdn博客 shuangde800