有N个城市，然后直接给出这些城市之间的邻接矩阵，矩阵中-1代表那两个城市无道路相连，其他值代表路径长度。

如果一辆汽车经过某个城市，必须要交一定的钱(可能是过路费)。

现在要从a城到b城，花费为路径长度之和，再加上除起点与终点外所有城市的过路费之和。

求最小花费，如果有多条路经符合，则输出字典序最小的路径。

假设有

1--->2  2

2--->3  1

1--->3  3

求1到3的最小花费路径.

那么显然后两条路: 

1-->3   3

1-->2-->3  3

它们的花费是相同的，但是路径的字典序不同，“123”比“13”字典序要小，所以应当输出1-->2-->3.

由于刚开始学最短路，打印路径时参考了别人的代码。

#include<stdio.h>
#include<string.h>
#define INF 1<<25
const int N = 1000;
int path[N][N], d[N][N], tax[N];
//path[i][j]用来保存 i --> j 的最短路径中 i 的最优后驱（即最近），在Floyd三重循环时，一直更新path。
void Floyd(int n)
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            path[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(d[i][k] < INF && d[k][j] < INF)
                {
                    int temp = d[i][k] + d[k][j] + tax[k];
                    if(temp < d[i][j])
                    {
                        d[i][j] = temp;
                        path[i][j] = path[i][k];
                    }
                    else if(temp == d[i][j])
                    {
                        if(path[i][j] > path[i][k])
                            path[i][j] = path[i][k];
                    }
                }

            }
}

int main()
{
    int n, i, j, s, t;
    while(~scanf("%d",&n) && n)
    {
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
            {
                 scanf("%d",&d[i][j]);
                 if(d[i][j] == -1)
                    d[i][j] = INF;
            }
        for(i = 1; i <= n; i++)
            scanf("%d",&tax[i]);
        Floyd(n);
        while(~scanf("%d%d",&s,&t))
        {
            if(s == -1 && t == -1)   break;
            printf("From %d to %d :\n", s, t);
            printf("Path: %d",s);
            int temp = s;
            while(temp != t)
            {
                printf("-->%d",path[temp][t]);
                temp = path[temp][t];
            }
            printf("\n");
            printf("Total cost : %d\n",d[s][t]);
            printf("\n");
        }
    }
    return 0;
}