HDU 1385 Minimum Transport Cost(最短路，打印字典序路径)
题目大意：
有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
[cpp]
#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] = '\0';
//2.获取当前点的路径
pos=0;
dfs(now, str2);
str2[pos++] = origin+'0';
str2[pos] = '\0';
//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收费为0
SPFA(src);
printf("From %d to %d :\n",src,des);
printf("Path: ");
&nbs
补充：软件开发 , C++ ,
