一、學習目標

• 正確判斷 Dijkstra 的適用條件：邊權 ≥ 0。
• 熟練最小堆（priority_queue with greater） 的寫法與「鬆弛（relax）」流程。
• 能處理 單源到所有點、帶特殊狀態（一次折扣）等變形。
• 會做 路徑重建 與常見優化（early exit、多源初始化、距離下溢/上溢防護）。

二、觀念說明

• 核心：從源點 s 出發，維護一個「當前能到達的最短距離」集合，每次取距離最小的點 u，嘗試用 u 去鬆弛鄰邊 (u→v, w)：
• if dist[v] > dist[u] + w then dist[v] = dist[u] + w
• 資料結構：最小堆 priority_queue<pair<long long,int>, vector<...>, greater<...>> pq;
• 正確性前提：權重非負（否則可能還能被更短路徑更新）。
• 複雜度：
• O((n+m)logn)，用 adjacency list。
• 小技巧：
  • early exit：若只需到達單一 t，當 t 第一次彈出堆即為最短。
  • 多源：把多個源點距離設 0 一起推入堆。
  • 路徑重建：記 parent[v]=u，最後從目標倒推回源。
  • 64 位：距離用 long long，INF 用大到不溢位的常數（例如 4e18）。

三、CSES實戰演練

題目1:Shortest Routes I

原題:
https://cses.fi/problemset/task/1671

題意:
給定一張有向圖（n 點、m 邊），邊權非負。從節點 1 出發，輸出到每個節點的最短距離。若不可達，距離會維持為很大的數（常設為 INF）並輸出。

解題思路:

• 條件：邊權 ≥0 → 適用 Dijkstra。
• 以 adjacency list 儲存圖；用最小堆（priority_queue with greater）加速鬆弛。
• 距離使用 long long，初值 INF（如 4e18）。
• 每次從堆中取出目前距離最小的點 u，嘗試更新所有鄰點 v：if dist[v] > dist[u] + w(u,v) → 更新。
• 只需單源到所有點，不必重建路徑。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m; 
    cin >> n >> m;

    const long long INF = (long long)4e18;
    vector<vector<pair<int,int>>> g(n+1);
    for(int i=0;i<m;i++){
        int a,b,w; cin>>a>>b>>w;
        g[a].push_back({b,w});
    }

    vector<long long> dist(n+1, INF);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
    dist[1]=0; pq.push({0,1});

    while(!pq.empty()){
        auto [d,u]=pq.top(); pq.pop();
        if(d!=dist[u]) continue; // 已有更短解
        for(auto [v,w]: g[u]){
            if(dist[v] > d + w){
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }

    for(int i=1;i<=n;i++){
        cout << dist[i] << (i==n?'\n':' ');
    }
    return 0;
}

題目2:Flight Discount

原題:
https://cses.fi/problemset/task/1195

題意:
從節點 1 走到節點 n，你可以對 其中一條邊 使用折扣（價格 / 2，向下取整）。求最短距離。

解題思路:

• 狀態拆成兩層：
  • d0[v]：走到 v 且 尚未 使用折扣的最短距離。
  • d1[v]：走到 v 且 已經 使用折扣的最短距離。
• 對每條邊 (u→v, w) 做兩類轉移：
  • 不用折扣：d0[v] = min(d0[v], d0[u]+w)；d1[v] = min(d1[v], d1[u]+w)
  • 在此邊用折扣：d1[v] = min(d1[v], d0[u] + w/2)
• 用一個堆存 (距離, 節點, 是否已用折扣) 做 Dijkstra。

#include <bits/stdc++.h>
using namespace std;

struct State{
    long long d; int u; int used; // used=0/1
    bool operator<(State const& o) const { return d > o.d; }
};

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m; if(!(cin>>n>>m)) return 0;
    vector<vector<pair<int,int>>> g(n+1);
    for(int i=0;i<m;i++){
        int a,b,w; cin>>a>>b>>w;
        g[a].push_back({b,w});
    }

    const long long INF = (long long)4e18;
    vector<long long> d0(n+1, INF), d1(n+1, INF);
    priority_queue<State> pq;
    d0[1]=0; pq.push({0,1,0});

    while(!pq.empty()){
        auto [d,u,used]=pq.top(); pq.pop();
        if(used==0 && d!=d0[u]) continue;
        if(used==1 && d!=d1[u]) continue;

        for(auto [v,w]: g[u]){
            // 不用折扣
            if(used==0 && d0[v] > d + w){
                d0[v] = d + w;
                pq.push({d0[v], v, 0});
            }
            if(used==1 && d1[v] > d + w){
                d1[v] = d + w;
                pq.push({d1[v], v, 1});
            }
            // 這條邊使用折扣
            if(used==0){
                long long nd = d + (long long)w/2; // 向下取整
                if(d1[v] > nd){
                    d1[v] = nd;
                    pq.push({d1[v], v, 1});
                }
            }
        }
    }

    cout << d1[n] << "\n"; // 必須使用過一次折扣的最短距離
    return 0;
}

四、Leetcode實戰演練

題目1:Network Delay Time

原題:
https://leetcode.com/problems/network-delay-time/description/

題意:
給定有向邊 times[i] = {u, v, w} 表示 u→v 需要時間 w，總共有 n 個節點，從起點 k 發送訊號。訊號到達所有節點需要的最久時間是多少？若有節點不可達回傳 -1。

解題思路:

• 權重非負 → 單源最短路徑，用 Dijkstra。
• 算出從 k 到各點的 dist[i]，答案是 max(dist)；若存在 dist[i] 為 INF，回傳 -1。

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        const long long INF = (long long)4e18;
        vector<vector<pair<int,int>>> g(n+1);
        for(auto &e: times) g[e[0]].push_back({e[1], e[2]});

        vector<long long> dist(n+1, INF);
        priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
        dist[k]=0; pq.push({0,k});

        while(!pq.empty()){
            auto [d,u]=pq.top(); pq.pop();
            if(d!=dist[u]) continue;
            for(auto [v,w]: g[u]){
                if(dist[v] > d + w){
                    dist[v] = d + w;
                    pq.push({dist[v], v});
                }
            }
        }

        long long ans = 0;
        for(int i=1;i<=n;i++) ans = max(ans, dist[i]);
        return ans >= INF/2 ? -1 : (int)ans;
    }
};

題目2:Path With Minimum Effort

原題:
https://leetcode.com/problems/path-with-minimum-effort/

題意:
給定高度矩陣 h，從 (0,0) 走到 (n-1,m-1)。一步的費用為相鄰格高度差的絕對值。路徑的成本定義為沿途所有步驟費用的最大值。求使該「最大值」最小的路徑成本。

解題思路:

• 這是把「距離」定義成「到達該格時的最小可能最大邊權」。
• 仍可用 Dijkstra：
  • 從起點開始，對鄰格的代價 w = |Δ高度|，新的距離 nd = max(dist[x][y], w)。
  • 若 dist[nx][ny] > nd 則更新。
• 也可用「二分答案 + BFS/並查集」，但 Dijkstra 寫起來直觀。

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& h) {
        int n = h.size(), m = h[0].size();
        const int INF = 1e9;
        vector<vector<int>> dist(n, vector<int>(m, INF));
        using T = tuple<int,int,int>; // d,x,y
        priority_queue<T, vector<T>, greater<T>> pq;

        auto inside = [&](int x,int y){return x>=0&&x<n&&y>=0&&y<m;};
        int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};
        dist[0][0]=0; pq.push({0,0,0});

        while(!pq.empty()){
            auto [d,x,y]=pq.top(); pq.pop();
            if(d!=dist[x][y]) continue;
            if(x==n-1 && y==m-1) return d; // 最早彈出即最優
            for(int k=0;k<4;k++){
                int nx=x+dx[k], ny=y+dy[k];
                if(!inside(nx,ny)) continue;
                int w = abs(h[nx][ny]-h[x][y]);
                int nd = max(d, w);
                if(dist[nx][ny] > nd){
                    dist[nx][ny] = nd;
                    pq.push({nd, nx, ny});
                }
            }
        }
        return dist[n-1][m-1];
    }
};