ZOJ - 1456 FLOYD路径输出

题目大意

有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;
}