題意#
世界上有 \(n\) 座城市以及 \(m\) 條單向航班。你的任務是計算出從起始城市 Syrjälä（編號 1）出發，抵達其他所有城市各自需要的最短飛行距離。
思路#
這是一道單源最短路徑（Single-Source Shortest Path）的裸題，也是 Dijkstra 演算法最純粹的展現舞台。由於題目中給定的航班飛行距離（邊權重）不可能為負數，而且城市與航班數量都達到了 \(10^5\) 級別，我們必須準備最經典的 Priority Queue 優先佇列來優化我們的 BFS 搜索。
演算法的核心概念很直覺，就像是倒滿水的杯子向外溢出：
- 準備一個
dis陣列紀錄從起點到各城市的最短距離，最初除了起點為0外，其他地方都設為超級大（無限大）。 - 將每次更新距離的地點連同最新的距離丟進 Min-Heap 優先佇列裡。
- 每次從佇列中取出「目前離起點最近」的城市，然後用已經確定的最短距離向外「鬆弛（Relax）」它相鄰的城市。如果有城市透過這條新路徑變得更近了，就更新
dis並把它推進佇列中。 - 為了防止過期的長路徑在佇列裡浪費時間，我們可以用一個
vis陣列，只要某個城市的最短距離被從佇列中確立拿出來過了，之後再遇到就直接跳過。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n, m; cin >> n >> m;
vector<vector<PII>> g(n+1);
// 建立有向圖
while (m--) {
int a, b, w; cin >> a >> b >> w;
g[a].pb({b, w});
}
// vis 陣列確保每個節點只被處理最短的那次，dis 陣列預設無限大
vector<int> vis(n+1), dis(n+1, INF);
// Min-Heap 優先佇列，讓距離最小的點優先浮上水面 pop 出來
priority_queue<PII, vector<PII>, greater<PII>> pq;
// 從起點（節點 1）出發
pq.push({0, 1}); dis[1] = 0;
while (pq.size()) {
auto [nowDist, nowID] = pq.top(); pq.pop();
// 稍早放入的較長過期路徑直接拋棄
if (vis[nowID]) continue;
vis[nowID] = 1; // 確立起點到 nowID 的最短路徑
// 嘗試合併周圍的路徑（鬆弛操作）
for (auto &[toID, toDist] : g[nowID]) {
if (dis[nowID]+toDist < dis[toID]) {
dis[toID] = dis[nowID] + toDist;
// 更新後推入佇列以便後續展開
pq.push({dis[toID], toID});
}
}
}
// 印出從起點 1 飛往所有城市分別的最短距離
for (int i = 1; i <= n; i++) cout << dis[i] << ' ';
}
