相当于一道模板题吧。
学会了floyed 的路径保存的方法。
代码来源网络。
如下:
#include <iostream> #include <stdio.h> #include <memory.h> #include <queue> using namespace std; const int INF = 99999999; const int N = 505; int map[N][N], tax[N], path[N][N]; 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, len; for(k = 1; k <= n; k++) { for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) { len = map[i][k] + map[k][j] + tax[k]; if(map[i][j] > len) { map[i][j] = len; path[i][j] = path[i][k]; //标记到该点的前一个点 } else if(len == 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; }