leetcode 743 网络延迟时间

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

有 N 个网络节点，标记为 1 到 N。

给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。

现在，我们向当前的节点 K 发送了一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。

注意:

N 的范围在 [1, 100] 之间。
K 的范围在 [1, N] 之间。
times 的长度在 [1, 6000] 之间。
所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100。

计算所有节点间的距离

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        vector<vector<int>> map(N, vector<int>(N, 999));
        for (auto i = 0; i < N; ++i) {
            map[i][i] = 0;
        }

        for (auto time: times) {
            auto u = time[0];
            auto v = time[1];
            auto w = time[2];
            map[u - 1][v - 1] = w;
        }

        for(auto i = 0; i < N; ++i)
            for (auto j = 0; j < N; ++j)
                for (auto m = 0; m < N; ++m)
                    map[j][m] = min(map[j][m], map[j][i] + map[i][m]);

        int result = *max_element(map[K - 1].begin(), map[K - 1].end());
        return result == 999 ? -1: result;
    }
};