学步园

/*可以用path来记录前驱结点或者是后继结点。而对于输出最小的字典序必须要记录后继结点。
主要是path记录路径方法的应用。
而对于点权，可以直接进行加处理。然后一遍floyd即可。*/
#include <stdio.h>
#include <cstring>
const int maxn=101;
int map[maxn][maxn];
int cost[maxn];
int path[maxn][maxn];
int main()
{
    int n;
    while(scanf("%d",&n)==1 && n)
    {
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
            {
                scanf("%d",&map[i][j]);
                path[i][j]=j;
            }
        for(int i=1; i<=n; i++)
            scanf("%d",&cost[i]);
        for(int k=1; k<=n; k++)
            for(int i=1; i<=n; i++)
            {
                if(map[i][k]==-1||i==k) continue;
                for(int j=1; j<=n; j++)
                {
                    if(map[k][j]==-1||j==k) continue;
                    if(i==j) continue;
                    if(map[i][j]==-1||map[i][k]+map[k][j]+cost[k]<map[i][j])
                    {
                        map[i][j]=map[i][k]+map[k][j]+cost[k];
                        path[i][j]=path[i][k];
                    }
                    else if(map[i][k]+map[k][j]+cost[k]==map[i][j])
                    {
                        if(path[i][k]<path[i][j])
                            path[i][j]=path[i][k];
                    }
                }
            }
        int s,e;
        while(scanf("%d%d",&s,&e)==2)
        {
            if(s==-1&&e==-1) break;
            printf("From %d to %d :\n",s,e);
            int ss=s;
            if(s==e)
            {
                printf("Path: %d\n",s);
                printf("Total cost : 0\n");
            }
            else
            {
                printf("Path: %d",s);
                while(path[s][e]!=e)
                {
                    printf("-->%d",path[s][e]);
                    s=path[s][e];
                }
                printf("-->%d\n",e);
                printf("Total cost : %d\n",map[ss][e]);
            }
            printf("\n");
        }
    }
    return 0;
}