图 Dijkstra / Bellman-Ford / Floyd-Warshell Leetcode 743-Network Delay Time

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

Disjstra

class Solution {
public:
    using pii = pair<int, int>; 

    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        
        vector<vector<pii> > eg(n+1);
        
        for(auto& E: eg) E.reserve(n+1);

        vector<int> vis(n+1);
        
        int ans = 0;

        for(auto& x: times){
            eg[x[0]].emplace_back(x[1], x[2]);
        }
        priority_queue<pii, vector<pii>, greater<pii> > q;
        q.emplace(0, k);
        while(q.size()){
            auto [time, now] = q.top(); q.pop();
          
            if(vis[now])continue;

            ans = max(ans, time);
            vis[now] = true;
            for(auto [next, nextTime]: eg[now]){
                if(vis[next] == false) q.emplace(nextTime + time, next);
            }

        }
        return count(begin(vis)+1, end(vis), true) == n ? ans : -1;
    }
};
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

class Solution {
public:
    int networkDelayTime(vector<vector<int>> &times, int n, int k) {
        const int inf = INT_MAX / 2;
        vector<vector<pair<int, int>>> g(n);
        for (auto &t : times) {
            int x = t[0] - 1, y = t[1] - 1;
            g[x].emplace_back(y, t[2]);
        }

        vector<int> dist(n, inf);
        dist[k - 1] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
        q.emplace(0, k - 1);
        while (!q.empty()) {
            auto p = q.top();
            q.pop();
            int time = p.first, x = p.second;
            if (dist[x] < time) {   //??????
                continue;
            }
            for (auto &e : g[x]) {
                int y = e.first, d = dist[x] + e.second;
                if (d < dist[y]) {
                    dist[y] = d;
                    q.emplace(d, y);
                }
            }
        }

        int ans = *max_element(dist.begin(), dist.end());
        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
33
34
35

Bellman-Ford

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        const int INF = 0x3f3f3f3f;
        vector<int> dist(N+1, INF); // 到起点的最短距离
        //vector backup(N+1); // 防止串联

        dist[K] = 0;
        for (int i = 1; i <= N; i++){ // 松弛N 次
            for (auto &t: times){ // 枚举所有边
                int u = t[0], v=t[1], w = t[2];
                dist[v] = min(dist[v], dist[u]+w); // 更新最短路
            }
        }
        int ans = *max_element(dist.begin() + 1, dist.end());
        return ans == INF ? -1 : ans; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Floyd-Warshall

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        const int INF = 0x3f3f3f3f;
        vector<vector<int>> d(N+1, vector<int>(N+1, INF));
        for (int i = 1; i<=N; i++) d[i][i] = 0;

        for (auto &t: times){
            d[t[0]][t[1]] = min(d[t[0]][t[1]], t[2]);
        }

        for (int k = 1; k<=N; k++){
            for (int i = 1; i<=N; i++){
                for (int j =1; j<=N; j++){
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
        int ans = 0;
        for (int i =1; i<=N; i++){
            ans = max(ans, d[K][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