【題目敘述】https://vjudge.net/problem/POJ-2387
【解題想法】Dijkstra algorothm 計算最短路徑
- 起點 N，終點 1。
- Data input：T 條「雙向」路徑。
- 接著，用priority_queue (由小到大排序) 實作Dijkstra algorothm，計算最短路徑。
- dis[i]：除了紀錄從起點走到「頂點-i」的最短距離，也可以用來判斷一個頂點是否已經被拓展過。
- ⚠️注意：POJ 平台支援的是 C++98，不支援auto自動變數類型。
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
struct cmp{
bool operator()(pair<int, int> x, pair<int, int> y){
return x.first > y.first;
}
};
int n, t, a, b, c, dis[1005];
vector <pair<int, int> > v[1005];
priority_queue <pair<int, int>, vector <pair<int, int> >, cmp> pq;
pair <int, int> now, nxt;
int main() {
cin >> t >> n;
for (int i = 0; i < t; i++){
cin >> a >> b >> c;
v[a].push_back({c, b});
v[b].push_back({c, a});
}
pq.push({0, n});
memset(dis, -1, sizeof(dis));
while (!pq.empty()){
now = pq.top();
pq.pop();
if (dis[now.second] == -1){
dis[now.second] = now.first;
for (int i = 0; i < v[now.second].size(); i++){
nxt = v[now.second][i];
if (dis[nxt.second] == -1) pq.push({now.first+nxt.first, nxt.second});
}
}
}
cout << dis[1] << "\n";
}