Leetcode 743 网络延迟时间

遇到一个特别好的题目，以及特别的好的题解，借鉴一下，做个笔记

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

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

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

题解：https://leetcode.cn/problems/network-delay-time/solutions/887186/wang-luo-yan-chi-shi-jian-dan-yuan-zui-d-m1m3/

dfs模版：

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}

dfs:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<unordered_map<int, int>> mp;

    void dfs(int cur_node, vector<int>& r, int cur_t) {
        if (cur_t < r[cur_node]) {
            r[cur_node] = cur_t;
            for (auto item : mp[cur_node]) {
                dfs(item.first, r, cur_t + item.second)
            }
        }
    }

    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        mp.resize(n + 1);
        for (auto item : times) {
            mp[item[0]][item[1]] = item[2];
        }

        vector<int> r(n + 1, INT_MAX);
        dfs(k, r, 0);

        int ans = 0;
        for (int i = 1; i <= n; i ++) {
            ans = max(ans, r[i]);
        }
        if (ans == INT_MAX) return -1;
        else return ans;
    }
};

bfs:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<unordered_map<int, int>> mp;

    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        mp.resize(n + 1);
        for (auto& edge : times) {
            mp[edge[0]][edge[1]] = edge[2];
        }

        vector<int> r(n + 1, INT_MAX);
        r[k] = 0;
        queue<pair<int, int>> q;

        q.push({k, 0});
        while(!q.empty()) {
            int m = q.size();
            while (m --) {
                auto cur = q.front();
                q.pop();
                for (auto item : mp[cur.first]) {
                    if (r[item.first] > cur.second + item.second) {
                        r[item.first] = cur.second + item.second;
                        q.push({item.first, r[item.first]});
                    }
                }
            }
        }

        int ans = 0;
        for (int i = 1; i <= n; i ++) {
            ans = max(ans, r[i]);
        }
        if (ans == INT_MAX) return -1;
        else return ans;
    }
};

Dijkstra:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    vector<unordered_map<int, int>> mp;

    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        mp.resize(n + 1);
        for (auto& edge : times) {
            mp[edge[0]][edge[1]] = edge[2];
        }

        vector<int> r(n + 1, INT_MAX);
        r[k] = 0;

        unordered_set<int> s;
        
        while (true) {
            int cur = -1, tim = INT_MAX;
            for (int i = 1; i <= n; i ++) {
                if (r[i] < tim && s.find(i) == s.end()) {
                    cur = i;
                    tim = r[i];
                }
            }

            if (cur == -1) break;

            s.emplace(cur);
            for (auto& edg : mp[cur]) {
                r[edg.first] = min(r[edg.first], edg.second + tim);
            }
        }

        int ans = 0;
        for (int i = 1; i <= n; i ++) {
            ans = max(ans, r[i]);
        }
        if (ans == INT_MAX) return -1;
        else return ans;
    }
};

Floyd:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#define MAXVALUE 0x3f3f3f3f
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<int>> mp(n + 1, vector<int>(n + 1, MAXVALUE));

        for (int i = 1; i <= n; i ++) {
            mp[i][i] = 0;
        }
        for (auto& edge : times) {
            mp[edge[0]][edge[1]] = edge[2];
        }

        for (int k = 1; k <= n; k ++) {
            for (int i = 1; i <= n; i ++) {
                for (int j = 1; j <= n; j ++) {
                    mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i ++) {
            ans = max(ans, mp[k][i]);
        }
        if (ans == MAXVALUE) return -1;
        else return ans;
    }
};