hdu 1385 Minimum Transport Cost

floyd+字典序

[cpp] 
#include"stdio.h" 
#include"string.h" 
#define INF 99999999 
int map[505][505],tax[505],path[505][504]; 
int n; 
void init() 
{ 
    int i,j; 
    for(i=1;i<=n;i++) 
        for(j=1;j<=n;j++) 
            if(i==j)map[i][j]=0; 
            else map[i][j]=INF; 
} 
void input() 
{ 
    int i,j,k; 
    for(i=1;i<=n;i++) 
        for(j=1;j<=n;j++) 
        { 
            scanf("%d",&k); 
            if(k!=-1)map[i][j]=k; 
            path[i][j]=j; 
        } 
    for(i=1;i<=n;i++) 
        scanf("%d",&tax[i]); 
} 
void floyd() 
{ 
    int i,j,k,t; 
    for(k=1;k<=n;k++) 
    { 
        for(i=1;i<=n;i++) 
        { 
            for(j=1;j<=n;j++) 
            { 
                t=map[i][k]+map[k][j]+tax[k]; 
                if(map[i][j]>t) 
                { 
                    map[i][j]=t; 
                    path[i][j]=path[i][k]; 
                } 
                else if(t==map[i][j]) 
                { 
                    if(path[i][j]>path[i][k]) 
                        path[i][j]=path[i][k]; 
                } 
            } 
        } 
    } 
} 
void output() 
{ 
    int i,j,k; 
    while(scanf("%d%d",&i,&j)) 
    { 
        if(i==-1&&j==-1)break; 
        printf("From %d to %d :\n",i,j); 
        printf("Path: %d",i); 
        k=i; 
        while(k!=j) 
        { 
            printf("-->%d",path[k][j]); 
            k=path[k][j]; 
        } 
        printf("\n"); 
        printf("Total cost : %d\n\n",map[i][j]); 
    } 
} 
int main() 
{ 
    while(scanf("%d",&n),n) 
    { 
        init(); 
        input(); 
        floyd(); 
        output(); 
    } 
    return 0; 
}