hdu 1385

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 2005
#define INF 0x3f3f3f3f
#define LL __int64
#define INF 0x3f3f3f3f
int ma[N][N],d[N],vis[N],pre[N],dis[N][N],b[N];
int judge(int x,int y,int v0)
{
    int s1[2000],s2[2000],len1 = 0,len2 = 0,i,j;
    s1[len1++] = y,s2[len2++] =y;
    while(y!=v0) {s1[len1++] = pre[y];y = pre[y];}
    s2[len2++] = x;
    while(x!=v0) {s2[len2++] = pre[x];x = pre[x];}
    for(i = len1-1,j = len2-1 ; i>=0&&j>=0 ; i--,j--)
        if(s1[i]<s2[j]) return 0;
        else if(s1[i]>s2[j]) return 1;
        if(i<0&&j>=0) return 0;
        else if(i>=0&&j<0) return 1;
    return 1;
}
void dijkstral(int v0,int n)
{
    int v,x,y,temp,i;
    for(i = 1 ; i <= n ; i++)
    {
        d[i] = dis[v0][i];
        if(d[i]!=INF) pre[i] = v0;
        vis[i] = 0;
    }
    d[v0] = 0;
    vis[v0] = 1;
    for(i = 1 ; i <= n ; i++)
    {
        temp = INF;
        for(y = 1 ; y <= n ;y++)
            if(!vis[y]&&temp>d[y]) temp = d[x=y];
        vis[x] = 1;
        for(y = 1 ; y <= n ; y++)
            if(!vis[y]&&d[x]+dis[x][y]<d[y])
            {
                 d[y] = d[x]+dis[x][y];
                 pre[y] = x;
            }
            else if(!vis[y]&&d[x]+dis[x][y]==d[y])//判断字典序
            {
                if(judge(x,y,v0)) pre[y] = x;
            }
    }
}
int main()
{
    int n,m,i,j,k,s,t;
    while(~scanf("%d",&n),n)
    {
        for(i = 1 ; i<= n ; i++)
            for(j = 1 ; j<= n ; j++)
            {
                scanf("%d",&ma[i][j]);
                if(ma[i][j] == -1) ma[i][j] = INF;
            }
            for(i = 1 ; i<= n ;i++) scanf("%d",&b[i]);
            while(~scanf("%d %d",&s,&t))
            {
                if(s==-1&&t==-1) break;
                for(i = 1 ; i<=n ; i++)
                {
                    for(j = 1 ; j <= n ;j++)
                        if(j!=s&&j!=t) dis[i][j] = ma[i][j]+b[j];
                    else dis[i][j] = ma[i][j];
                }
            dijkstral(s,n);
            printf("From %d to %d :
",s,t);
            printf("Path: %d",s);
            int sta[2000],i=0,p = t;
            while(p!=s){
                sta[i++] = p;
                p = pre[p];
            }
            for(j = i -1; j>=0 ; j--)
                printf("-->%d",sta[j]);
            printf("
Total cost : %d

",d[t]);
            }

    }
    return 0;
}