Leetcode刷題學習筆記–Shortest Path Faster Algorithm(SPFA)

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
    vector<int> dist(n, INT_MAX);
    dist[src] = 0;
    queue<int> q;
    q.push(src);
    unordered_map<int, unordered_map<int, int>> m; // <from, <to, cost>>
    for(auto& f : flights)
        m[f[0]].insert({f[1], f[2]});

    vector<int> prev;
    while(!q.empty() && k >= 0) {
        prev = dist;
        for(int i = q.size(); i > 0; --i) {
            int cur = q.front(); q.pop();
            for(auto& item : m[cur]) {
                // 計算距離時，使用沒被更新的prev，因為才不會重複更新。
                if(prev[cur] + item.second < prev[item.first]) {
                    // 因為是選最短距離。
                    dist[item.first] = min(dist[item.first], prev[cur] + item.second);
                    // 紀錄更新過的node
                    q.push(item.first);
                }
            }
        }
        k--;
    }        
    return dist[dst] == INT_MAX ? -1 : dist[dst];
}

int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    vector<int> arr(n + 1, INT_MAX);
    arr[k] = 0;
    unordered_map<int, unordered_map<int, int>> m; // <from, <to, time>>
    for(auto& t : times)
        m[t[0]].insert({t[1], t[2]});
    queue<int> q;
    q.push(k);
        
    vector<int> prev;
    while(!q.empty()) {
        prev = arr;
        for(int i = q.size(); i > 0; --i) {
            int cur = q.front(); q.pop();
            for(auto& item : m[cur]) {
                if(prev[cur] + item.second < prev[item.first]) {
                    arr[item.first] = min(arr[item.first], prev[cur] + item.second);
                    q.push(item.first);
                }
            }
        }
    }
        
    int rtn = -1;
    for(int i = 1; i <= n; ++i) {
        if(i == k) continue;
        if(arr[i] == INT_MAX) return -1;
        rtn = max(rtn, arr[i]);
    }
        
    return rtn;
}