The cost of the transportation on the path between these cities, and

a certain tax which will be charged whenever any cargo passing through one city, except for the source and the destination cities.

You must write a program to find the route which has the minimum cost.

Input

First is N, number of cities. N = 0 indicates the end of input.

The data of path cost, city tax, source and destination cities are given in the input, which is of the form:

a11 a12 ... a1N
a21 a22 ... a2N
...............
aN1 aN2 ... aNN
b1  b2  ... bN

c d
e f
...
g h

where aij is the transport cost from city i to city j, aij = -1 indicates there is no direct path between city i and city j. bi represents the tax of passing through city i. And the cargo is to be delivered from city c to city d, city e to city f, ..., and g = h = -1. You must output the sequence of cities passed by and the total cost which is of the form:

Output

From c to d :
Path: c-->c1-->......-->ck-->d
Total cost : ......
......

From e to f :
Path: e-->e1-->..........-->ek-->f
Total cost : ......

Note: if there are more minimal paths, output the lexically smallest one. Print a blank line after each test case.

Sample Input

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

Sample Output

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

求两个城市间的最小费用，如果经过某个城镇还要交税，起始点和终点除外。

路径要求字典序最小，path[i][j]记录从i到j的第二个元素的编号。

#include"stdio.h"
#include"string.h"
#include"vector"
#include"queue"
#include"iostream"
#include"algorithm"
using namespace std;
#define N 1005
const int inf=1000000;
int n,s,t;
int g[N][N],c[N];
int path[N][N];
int min(int a,int b)
{
    return a<b?a:b;
}
void Floyd()
{
    int i,j,k;
    for(k=1;k<=n;k++)
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(c[k]+g[i][k]+g[k][j]<g[i][j])
                {
                    g[i][j]=g[i][k]+g[k][j]+c[k];
                    path[i][j]=path[i][k];
                }
                else if(c[k]+g[i][k]+g[k][j]==g[i][j])
                {
                    path[i][j]=min(path[i][j],path[i][k]);
                }
            }
        }
    }
}
int main()
{
    int i,j;
    while(scanf("%d",&n),n)
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                path[i][j]=j;
                scanf("%d",&g[i][j]);
                if(g[i][j]==-1)
                    g[i][j]=inf;
            }
        for(i=1;i<=n;i++)
            scanf("%d",&c[i]);
        while(scanf("%d%d",&s,&t),s!=-1||t!=-1)
        {
            Floyd();
            printf("From %d to %d :\n",s,t);
            printf("Path: %d",s);
            int tmp=s;
            while(tmp!=t)
            {
                tmp=path[tmp][t];
                printf("-->%d",tmp);
            }
            printf("\nTotal cost : %d\n\n",g[s][t]);
        }
    }
    return 0;
}

zoj 1456 Minimum Transport Cost （Floyd+路径记录）