鏈接：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 <iostream>
#include <memory.h>
#include <string>
#include <istream>
#include <sstream>
#include <vector>
#include <stack>
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<int> 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;elseMap[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;
}
