floyd
#include<stdio.h> #include<string.h> #define MAX 0xffffff int map[1005][1005]; int inc[1005]; int path[1005][1005]; int main() { int n; while(scanf("%d",&n),n){ int i,j; for(i=0;i<n;i++){ for(j=0;j<n;j++){ scanf("%d",&map[i][j]); if(map[i][j]==-1) map[i][j]=MAX; } } for(i=0;i<n;i++){ for(j=0;j<n;j++){ path[i][j]=j; } } for(i=0;i<n;i++) scanf("%d",&inc[i]); int k; for(k=0;k<n;k++){ for(i=0;i<n;i++){ for(j=0;j<n;j++){ int t=map[i][k]+map[k][j]+inc[k]; if(t<map[i][j]){ 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]; } } } } int begin,end; while(scanf("%d%d",&begin,&end),!(begin==-1&&end==-1)){ printf("From %d to %d :\n",begin,end); printf("Path: "); begin--; end--; printf("%d",begin+1); for(i=begin;i!=end;i=path[i][end]){ printf("-->%d",path[i][end]+1); } puts(""); printf("Total cost : %d\n\n",map[begin][end]); //printf("-->%d\n",end+1); } } return 0; }