大意：
有N个城市，然后直接给出这些城市之间的邻接矩阵，矩阵中-1代表那两个城市无道路相连，其他值代表路径长度。
如果一辆汽车经过某个城市，必须要交一定的钱(可能是过路费)。
现在要从a城到b城，花费为路径长度之和，再加上除起点与终点外所有城市的过路费之和。
求最小花费，如果有多条路经符合，则输出字典序最小的路径。
思路：
Floyd求最短路，打印路径即可。
1 /*------------------------------------------------------------------*/ 2 3 const int maxn = 1000; 4 int n, s, e; 5 int path[maxn][maxn]; 6 int b[maxn]; 7 int rode[maxn][maxn]; 8 9 void Solve() 10 { 11 while(~scanf("%d", &n) && n) 12 { 13 for(int i = 1; i <= n; ++i) 14 { 15 for(int j = 1; j <= n; ++j) 16 { 17 scanf("%d", &path[i][j]); 18 if(path[i][j] == -1) 19 { 20 path[i][j] = INF; 21 } 22 rode[i][j] = j; 23 } 24 } 25 for(int i = 1; i <= n; ++i) 26 { 27 scanf("%d", &b[i]); 28 } 29 for(int k = 1; k <= n; ++k) 30 { 31 for(int i = 1; i <= n; ++i) 32 { 33 for(int j = 1; j <= n; ++j) 34 { 35 if(path[i][k]+path[k][j]+b[k] < path[i][j]) 36 { 37 path[i][j] = path[i][k]+path[k][j]+b[k]; 38 rode[i][j] = rode[i][k]; 39 } 40 else if(path[i][j] == path[i][k]+path[k][j]+b[k] && rode[i][j] > rode[i][k]) 41 { 42 rode[i][j] = rode[i][k]; 43 } 44 } 45 } 46 } 47 while(~scanf("%d%d", &s, &e)) 48 { 49 if(s == -1 && e == -1) 50 break; 51 printf("From %d to %d : Path: %d", s, e, s); 52 int u = s, v = e; 53 while(s != e) 54 { 55 printf("-->%d", rode[s][e]); 56 s = rode[s][e]; 57 } 58 printf(" "); 59 printf("Total cost : %d ", path[u][v]); 60 } 61 } 62 } 63 64 /*------------------------------------------------------------------*/