LeetCode743 网络延迟时间(Dijkstra存档)

发表于 | 分类于 |
字数统计: 409 | 阅读时长 ≈ 2

链接: https://leetcode.cn/problems/network-delay-time/

题意

给定一个网络连接图，其中有n个节点，求所有k到所有节点的最短距离的最大值

解法

单源最短路径，使用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
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        const int inf = 0x7f7f7f;
        vector<vector<int>> g(n + 1, vector<int>(n + 1, inf));
        for (auto idx: times) {
            g[idx[0]][idx[1]] = idx[2];
        }
        vector<int> vis(n + 1), dis(n + 1, inf);
        dis[k] = 0;
        while(true) {
            int v = -1;
            for (int i = 1; i <= n; i++) {
                if (!vis[i] && (v == -1 || dis[i] < dis[v])) {
                    v = i;
                }
            }
            if (v == -1) break;
            vis[v] = 1;
            for (int i = 1; i <= n; i++) {
                dis[i] = min(dis[i], dis[v] + g[v][i]);
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = max(ans, dis[i]);
        }
        return ans == inf ? -1 : ans;

    }
};

优先队列版

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
typedef pair<int, int> pii;
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        const int inf = 0x7f7f7f;
        vector<vector<pii>> g(n + 1);
        for (auto idx: times) {
            g[idx[0]].push_back({idx[1], idx[2]});
        }
        vector<int> vis(n + 1), dis(n + 1, inf);
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.push({0, k});
        dis[k] = 0;
        while(pq.size()) {
            auto top = pq.top();
            pq.pop();
            if (dis[top.second] < top.first) continue;
            for (auto idx: g[top.second]) {
                if (dis[idx.first] > dis[top.second] + idx.second) {
                    dis[idx.first] = dis[top.second] + idx.second;
                    pq.push({dis[idx.first], idx.first});
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = max(ans, dis[i]);
        }
        return ans == inf ? -1 : ans;

    }
};