本文主要是介绍hdu Minimum Transport Cost(按字典序输出路径)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=1385
求最短路，要求输出字典序最小的路径。
spfa：拿一个pre[]记录前驱，不同的是在松弛的时候，要考虑和当前点的dis值相等的情况，解决的办法是dfs找出两条路径中字典序较小的，pre[]去更新。把路径当做字符串处理。
我只用之前的pre去更新当前点，并没考虑到起点到当前点的整个路径，其实这样并不能保证是字典序最小。wa了N次，于是乎搜了下题解，发现用spfa解的很少，看到了某大牛的解法如上，感觉很赞的想法。
#include <stdio.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#define LL long long
#define _LL __int64
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 110;int n;
int tax[maxn];
int Map[maxn][maxn];
int dis[maxn],inque[maxn];
int pre[maxn];
int pos = 0;void dfs(int u, char *s)
{if(u == -1)return;dfs(pre[u],s);s[pos++] = u+'0';
}bool solve(int v, int u)
{char s1[maxn],s2[maxn];//寻找先前的路径pos = 0;dfs(v,s1);s1[pos] = '\0';//寻找由u更新的路径pos = 0;dfs(u,s2);s2[pos++] = v+'0';s2[pos] = '\0';if(strcmp(s1,s2) > 0) return true;return false;}int spfa(int s, int t)
{queue <int> que;memset(dis,INF,sizeof(dis));memset(inque,0,sizeof(inque));memset(pre,-1,sizeof(pre));dis[s] = 0;inque[s] = 1;que.push(s);while(!que.empty()){int u = que.front();que.pop();inque[u] = 0;for(int v = 1; v <= n; v++){if(Map[u][v] > 0){int tmp = dis[u] + Map[u][v] + tax[v];if(tmp < dis[v])//直接更新{dis[v] = tmp;pre[v] = u;if(!inque[v]){inque[v] = 1;que.push(v);}}else if(tmp == dis[v] && solve(v,u)){pre[v] = u;}}}}return dis[t];
}void output(int s, int t)
{int res[maxn];int cnt = 0;int tmp = t;while(pre[tmp] != -1){res[cnt++] = tmp;tmp = pre[tmp];}res[cnt] = s;printf("Path: ");for(int i = cnt; i >= 1; i--)printf("%d-->",res[i]);printf("%d\n",res[0]);
}int main()
{while(~scanf("%d",&n) && n){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++)scanf("%d",&Map[i][j]);}for(int i = 1; i <= n; i++)scanf("%d",&tax[i]);int u,v;while(~scanf("%d %d",&u,&v)){if(u == -1 && v == -1) break;int tmp1 = tax[u];//备份int tmp2 = tax[v];tax[u] = 0;tax[v] = 0;printf("From %d to %d :\n",u,v);int ans = spfa(u,v);output(u,v);printf("Total cost : %d\n\n",ans);//恢复备份tax[u] = tmp1;tax[v] = tmp2;}}return 0;
}
floyd:pre[i][j]记录i到j路径上距离i最近的点，输出路径时按pre正向输出。感觉floyd很强大啊，还可以这样记录路径。
#include <stdio.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <stack>
#include <queue>
#define LL long long
#define _LL __int64
using namespace std;const int INF = 0x3f3f3f3f;
const int maxn = 110;
int Map[maxn][maxn];
int tax[maxn];
int pre[maxn][maxn];
int n;void floyd()
{//初始化for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)pre[i][j] = j;for(int k = 1; k <= n; k++){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(Map[i][k] > 0 && Map[k][j] > 0){int tmp = Map[i][k] + Map[k][j] + tax[k];if(tmp < Map[i][j]) //小于直接更新{Map[i][j] = tmp;pre[i][j] = pre[i][k];}else if(tmp == Map[i][j]) {pre[i][j] = min(pre[i][k],pre[i][j]);}}}}}
}void output(int s, int t)
{printf("Path: ");int tmp = s;while(tmp != t){printf("%d-->",tmp);tmp = pre[tmp][t];}printf("%d\n",t);}int main()
{while(~scanf("%d",&n) && n){for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++){scanf("%d",&Map[i][j]);if(Map[i][j] == -1)Map[i][j] = INF;}for(int i = 1; i <= n; i++)scanf("%d",&tax[i]);int u,v;floyd();while(~scanf("%d %d",&u,&v)){if(u == -1 && v == -1) break;printf("From %d to %d :\n",u,v);output(u,v);printf("Total cost : %d\n\n",Map[u][v]);}}return 0;
}
这篇关于hdu Minimum Transport Cost(按字典序输出路径)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
