题目大意
有N个城市，城市之间只有最多一条运输路线，现在有一批货要从一个城市到另一个城市，运输费用分为两部分，第一是运输路线的费用，二是经过一个城市所交的税费。求费用的最小路径。
样例输入
5
0 3 22 -1 4
3 0 5 -1 -1
22 5 0 9 20
-1 -1 9 0 4
4 -1 20 4 0
5 17 8 3 1
1 3
3 5
2 4
-1 -1
0
第一行是一个数字N代表N个城市，接下来N行表示第i个城市到第j个城市运输路线的费用。紧接着一行是每个城市的税。接下来的每对数字代表要求的起点城市，到终点城市。-1 和 -1 代表输入结束。
样例输出
对于每对城市输出
From 1 to 3 :
Path: 1-->5-->4-->3
Total cost : 21
From 3 to 5 :
Path: 3-->4-->5
Total cost : 16
From 2 to 4 :
Path: 2-->1-->5-->4
Total cost : 17
题目分析
这题不难，就是用FLOYD，但是输出路径的话是个问题。我尝试着用书上的方法倒着输出，也就是path数组存的是上一个点的位置。发现无论如何都要RE。然后在网上看到一个好办法就是path数组存下一个点的位置。这样写起来也很简单，而且直接性的表达了路径 。
这题还有第二个问题，就是如果有多种选择，则要按字典序最小的路径输出。
这个时候在FLOYD改变路径的时候加上如下语句就搞定
if（A[i][j] == A[i][k] + A[k][j] + tax[k] && path[i][j] > path[i][k]）
path[i][j] = path[i][k];
这样就表示在同样的长度下选择字典序更小的点。
代码入下
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#define LL long long
#define eps 1e-6
#define CLR(x) memset(x,0,sizeof(x))
using namespace std;
const int maxn = 133;
const int inf = 1 << 29;
int n;
int A[maxn][maxn] , path[maxn][maxn] ;
int tax[maxn];
void floyd(){
for(int k = 1 ; k <= n ; k++){
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++){
if( A[i][k] + A[k][j] + tax[k] < A[i][j] ){
A[i][j] = A[i][k] + A[k][j] + tax[k];
path[i][j] = path[i][k];
}
else if(A[i][k] + A[k][j] + tax[k] == A[i][j]){
if(path[i][j] > path[i][k]){
path[i][j] = path[i][k];
}
}
}
}
}
}
int main(){
while(scanf("%d",&n)&& n){
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++){
scanf("%d",&A[i][j]);
path[i][j] = j;
if(A[i][j] == -1){
A[i][j] = inf;
}
}
for(int i = 1 ; i <= n ; i++){
scanf("%d",&tax[i]);
}
floyd();
while(1){
int a , b;
scanf("%d%d",&a,&b);
if(a == -1) break;
printf("From %d to %d :\n",a,b);
printf("Path: %d",a);
for(int i = a ; i != b ; i = path[i][b])
printf("-->%d",path[i][b]);
printf("\nTotal cost : %d\n\n",A[a][b]);
}
}
return 0;
}
