网络延迟时间

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
private:
    static const int N = 110, M = 6010;
    int h[N], e[M], w[M], ne[M], idx;
    int dist[N];
    bool st[N];

    void add(int a, int b, int weight) {
        e[idx] = b, w[idx] = weight, ne[idx] = h[a], h[a] = idx++;
    }

    void SPFA(int start) {
        queue<int> q;
        q.push(start);
        dist[start] = 0;

        while (!q.empty()) {
            int t = q.front(); q.pop();
            st[t] = false;

            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[t] + w[i]) {
                    dist[j] = dist[t] + w[i];
                    if (!st[j]) {
                        q.push(j); st[j] = true;
                    }
                }
            }
        }
    }

public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        memset(dist, 0x3f, sizeof(dist));
        memset(h, -1, sizeof(h));
        idx = 0;

        for (auto& edge: times) {
            int a = edge[0], b = edge[1], weight = edge[2];
            add(a, b, weight);
        }

        SPFA(k);

        int res = 1;
        for (int i = 1; i <= n; i++) res = max(res, dist[i]);
        if (res == 0x3f3f3f3f) res = -1;
        return res;
    }
};