Leetcode刷題學習筆記 – Dijkstra algorithm

class Solution {
    map<int, vector<pair<int, int>>> m;
    void dijstra(vector<int>& arr, int k) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        // 把weight放在pair第一個，是因為要讓priority_queue來排序。
        // 其中weight是start point到此點的距離。
        // 因為dijkstra最後是算出start point到每個點的最短距離
        pq.push(make_pair(0, k));
        arr[k] = 0;
        while(!pq.empty()) {
            int cur  = pq.top().second;
            int curt = pq.top().first;
            pq.pop();
            //if(curt > arr[cur]) continue;
            for(auto& adj : m[cur]) {
                if(arr[cur] + adj.first < arr[adj.second]) { // 從cur走到adj時間比原本還小
                    arr[adj.second] = arr[cur] + adj.first;
                    pq.push(make_pair(arr[adj.second], adj.second));
                }
            }
        }
    }
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        for(auto& time : times)
            m[time[0]].push_back(make_pair(time[2], time[1]));
        
        vector<int> arr(n + 1, INT_MAX);    // index從1開始方便記錄
        dijstra(arr, k);
        
        auto it = max_element(arr.begin() + 1, arr.end()); // 找max必須跳過第一個
        return *it == INT_MAX ? -1 : *it;
    }
};

class Solution {
    vector<vector<int>> dirs = {
                {-1,0},
        {0,-1},         {0,1},
                {1, 0}
    };
    
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        using pipii = pair<int, pair<int, int>>; // effort, y, x
        priority_queue<pipii, vector<pipii>, greater<pipii>> pq; // min-heap 每次都拿最小的effort路徑來更新
        pq.push({0, {0, 0}});
        
        int row = heights.size();
        int col = heights[0].size();
        vector<vector<int>> dist(row, vector<int>(col, INT_MAX));
        // 原點不需要effort
        dist[0][0] = 0;
        
        while(!pq.empty()) {
            auto p = pq.top(); pq.pop();
            int effort = p.first;
            int y = p.second.first;
            int x = p.second.second;
            // 已經有比這個路徑過來還要輕鬆的路
            if(dist[y][x] < effort) continue;
            if(y == row - 1 && x == col - 1) return effort;
            for(auto& d : dirs) {
                int nexty = d[0] + y;
                int nextx = d[1] + x;
                if(nexty < 0 || nextx < 0 || nexty == row || nextx == col) continue;
                int neweffort = abs(heights[y][x] - heights[nexty][nextx]);
                neweffort = max(neweffort, effort); // 從{y, x} 到{nexty, nextx} 的最大effort
                if(neweffort >= dist[nexty][nextx]) continue;
                dist[nexty][nextx] = neweffort;
                pq.push({neweffort, {nexty, nextx}});
            }
        }
        
        // never reach
        return 0;
    }
};