Minimum Transport Cost hdu 點權和邊權的最短路+輸出字典序最小的路徑

/*可以用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;
}