链接：https://oj.ahstu.cc/JudgeOnline/problem.php?id=2037
题意：
安科的夏天真是不一般的热，避免炎热，伍学长因此想为自己规划一个校园出行方案，使得从宿舍出发到校园的各个地方距离花费时间最短。我们已知校园一共有N个路口，标号为1的路口是宿舍所在地，2..N这N-1这几个标号分别是学校的N-1个地方，
M则表示安科共有M条路，N=M=0表示输入结束，接下来M行，每行有3个整数A,B,C（1<=A,B<=N,1<=C<=1000），表示在路口A与B之间有一条路，伍学长从A走到B花费时间C，伍学长来回用时相等,他现在想知道他分别到这N-1个路口的最小花费时间及步行方案
思路：
Dijkstra算法。
路径由Father数组记录每个位置最短路上的上一个结点。
每次成功松弛时，被松弛点的上一个结点便是用来松弛的点。
打印的时候用栈记录即可。
代码：
#include#include #include #include #include #include #include using namespace std;const int MAXN = 110;int n,m;int Map[MAXN][MAXN];int Dis[MAXN];int Vis[MAXN];int Father[MAXN];void init(){ for (int i = 1;i<=n;i++) { Dis[i] = Map[1][i]; Vis[i] = 0; Father[i] = 1; } Vis[1] = 1;}void Dijkstra(){ init(); for (int i = 1;i<=n;i++) { int w = -1,small = 999999; for (int j = 1;j<=n;j++) { if (Vis[j] == 0&&Dis[j] < small) { small = Dis[w = j]; } } Vis[w] = 1; for (int j = 1;j<=n;j++) { if (Vis[j] == 0&&Dis[j] > Dis[w] + Map[w][j]) { Father[j] = w; Dis[j] = Dis[w] + Map[w][j]; } } }}void Print_Path(int x){ stack Path; while (1) { Path.push(x); if (Father[x] == 1) break; x = Father[x]; } while (Path.size()) { cout << "->" << Path.top(); Path.pop(); } cout << endl;}int main(){ while (cin >> n >> m&&m) { int l, r, v; for (int i = 1;i<=n;i++) for (int j = 1;j<=n;j++) if (i == j) Map[i][j] = 0; else Map[i][j] = 999999; for (int i = 1; i <= m; i++) { cin >> l >> r >>v; Map[l][r] = Map[r][l] = v; } Dijkstra(); for (int i = 2;i<=n;i++) { cout << Dis[i] << ' '; cout << 1; Print_Path(i); } } return 0;}