743. Network Delay Time

dijkstra’s algorithm+heap O(NlogN + E) time O(N + E) space

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        vector<int> d(N + 1, INT_MAX);
        d[0] = d[K] = 0;
        vector<vector<pair<int, int>>> g(N + 1);
        for (const auto &t : times) {
            g[t[0]].emplace_back(t[1], t[2]);
        }
        auto cmp = [&d](int a, int b) { return d[a] == d[b] ? a < b : d[a] < d[b]; }; // 注意当d[a] == d[b]的时候set无法区分，所以只会保留一个数
        set<int, decltype(cmp)> q(cmp);
        q.insert(K);
        while (!q.empty()) {
            int u = *begin(q); q.erase(begin(q));
            for (auto [v, w] : g[u]) {
                if (d[u] + w < d[v]) {
                    q.erase(v);
                    d[v] = d[u] + w;
                    q.insert(v);
                }
            }
        }
        int res = 0;
        for (int x : d) {
            if (x == INT_MAX) return -1;
            res = max(res, x);
        }
        return res;
    }
};

错误实现，lambda会破坏pq内部结构！！

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        vector<unordered_map<int, int>> g(N + 1);
        g[0][K] = 0;
        for (const auto &e : times) {
            g[e[0]][e[1]] = e[2];
        }
        vector<int> d(N + 1, 1000000);
        d[0] = 0;
        auto cmp = [&d](int x, int y) {return d[x] > d[y];};
        priority_queue<int, vector<int>, decltype(cmp)> q(cmp);
        q.push(0);
        while (!q.empty()) {
            int u = q.top(); q.pop();
            while (!g[u].empty()) {
                auto it = g[u].begin();
                int v = it->first, t = it->second;
                d[v] = min(d[v], d[u] + t);
                q.push(v);
                g[u].erase(it);
            }
        }
        int res = 0;
        for (int x : d) {
            if (x >= 1000000) {
                return -1;
            }
            res = max(res, x);
        }
        return res;
    }
};

正确实现

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        vector<unordered_map<int, int>> g(N + 1);
        g[K][K] = 0;
        for (const auto &e : times) {
            g[e[0]][e[1]] = e[2];
        }
        vector<int> d(N + 1, INT_MAX);
        d[0] = d[K] = 0;
        using pii = pair<int, int>;
        priority_queue<pii, vector<pii>, greater<>> q;
        q.emplace(0, K);
        while (!q.empty()) {
            auto [w, u] = q.top(); q.pop();
            if (w != d[u]) continue;
            for (auto [v, w] : g[u]) {
                if (d[u] + w < d[v]) {
                    d[v] = d[u] + w;
                    q.emplace(d[v], v);
                }
            }
        }
        int res = 0;
        for (int x : d) {
            if (x >= INT_MAX) {
                return -1;
            }
            res = max(res, x);
        }
        return res;
    }
};