題目大意：
有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: ");
print_path(des);
printf("\nTotal cost : %d\n\n", d[des]);
// 恢復
charge[src]=tmp1, charge[des]=tmp2;
}
}
return 0;
}
2. Floyd 記錄路徑
[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 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 :\n",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\n\n", w[src][des]);
}
}
return 0;
}
