題意#
你要從城市 1（Syrjälä）搭飛機前往城市 \(n\)（Metsälä），任務是找出花費最少的飛行路線。
最特別的地方在於，你手上有一張「機票半價優惠券」，可以在整趟旅程中的任意一段航班使用，讓那段航班的價格直接折半（原本價格向下取整，例如價格 3 變 1）。不過這張優惠券只能使用一次，你要聰明地決定把它用在哪一段最划算。
思路#
這題是標準的單源最短路徑（Single-Source Shortest Path）變種題。\n\n我們要在無數條潛在的路線中，找出這條「因為某段機票半價而變得最便宜」的神奇路線。這代表決策有兩個：
- 我要走哪條路線？
- 我要在哪個航班上使用優惠券？
如果我們窮舉地嘗試每一段航班，假設正在看這段航班是從節點 \(A\) 飛往節點 \(B\)（費用為 \(W\)）。當我們決定在這裡用上半價券時，這趟旅行的總花費就會變成：
（從城市 1 到 \(A\) 的最短距離）+ \(W / 2\) + （從 \(B\) 到城市 \(n\) 的最短距離）
所以，我們其實只需要預先算出所有的「從 1 出發到各點的最短距離」以及「從各點出發到 \(n\) 的最短距離」，這可以直接做兩次 Dijkstra（Dijkstra）搞定。不過要注意，「從各點出發到 \(n\)」如果在一張單向圖上直接算會有點麻煩，但只要我們把所有邊的方向反轉（建一張反向圖），然後從 \(n\) 出發跑一次 Dijkstra，就能輕鬆拿到我們想要的結果了！
最後，我們只要把所有的邊都掃過一遍，透過上面的公式計算出最低花費即可。
程式碼#
#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>
// 將 Dijkstra 演算法獨立起來，方便我們對正向與反向圖呼叫
vector<int> Dijkstra(int start, vector<vector<PII>> &g) {
// 建立距離陣列與造訪紀錄，並將起始點設為 0
vector<int> vis(g.size()), dis(g.size(), INF);
priority_queue<PII, vector<PII>, greater<PII>> pq;
pq.push({0, start}); dis[start] = 0;
while (pq.size()) {
auto [nowDist, nowID] = pq.top(); pq.pop();
if (vis[nowID]) continue; // 稍早放入佇列的過期較長路徑不用處理
vis[nowID] = 1;
// 嘗試鬆弛相鄰邊
for (auto [toID, toDist] : g[nowID]) {
if (dis[toID] > dis[nowID] + toDist) {
dis[toID] = dis[nowID] + toDist;
pq.push({dis[toID], toID});
}
}
}
return dis; // 回傳由 start 開始到其他所有城市的最短距離
}
signed main() { WA();
int n, m; cin >> n >> m;
vector<vector<PII>> g(n+1), rg(n+1); // g 為正向圖, rg 為反向圖
vector<tuple<int, int, int>> e; // 儲存所有邊的資訊
while (m--) {
int a, b, w; cin >> a >> b >> w;
g[a].pb({b, w});
rg[b].pb({a, w}); // 將邊反向建構，用於反推從目的地出發的最短路
e.pb({w, a, b}); // 把邊存下來，之後方便枚舉
}
// dis1 算出「起點 1 到各點」的最短路
// dis2 算出「終點 n 到各點（反向圖）」的最短路，也就是原來從各點走到 n 的距離
vector<int> dis1 = Dijkstra(1, g), dis2 = Dijkstra(n, rg);
int mn = INF;
// 枚舉每一條邊，看看在這條路上使用半價折扣的總花費是否更便宜
for (auto [w, a, b] : e) {
// 確認這條邊確實有被路徑連接過
if (dis1[a] != INF && dis2[b] != INF) mn = min((w>>1) + dis1[a] + dis2[b], mn);
}
cout << mn << '\n';
}
