leetcode 743 - Network Delay Time

https://leetcode.com/problems/network-delay-time/
https://leetcode.com/problems/network-delay-time/discuss/283711/Python-Bellman-Ford-SPFA-Dijkstra-Floyd-clean-and-easy-to-understand

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Example 2:

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
Example 3:

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

Constraints:

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//Dijikstra: O(ElogE), priority queue
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<vector<int>>> graph(n+1);

for (auto &time : times)
graph[time[0]].push_back({time[1], time[2]}); //{node, edge_len}

vector<int> path(n+1, INT_MAX);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; //{path_len, node}

pq.push({0, k});

while (!pq.empty()) {
auto p = pq.top(); pq.pop();

if (p.first >= path[p.second]) continue;

path[p.second] = p.first;

for (auto &edge : graph[p.second])
pq.push({p.first + edge[1], edge[0]});
}

int ans = INT_MIN;

for (int i = 1; i < (int)path.size(); i++) {
if (path[i] == INT_MAX) return -1;
ans = max(ans, path[i]);
}

return ans;
}
};

//Bellman-Ford; O(VE)
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<int> distance(n+1, INT_MAX);

distance[k] = 0;

for (int i = 1; i <= n; i++) {
for (auto &time : times) {
int u = time[0];
int v = time[1];
int w = time[2];

if (distance[u] != INT_MAX)
distance[v] = min(distance[v], distance[u] + w);
}
}

int t = 0;

for (int i = 1; i <= n; i++) {
if (distance[i] == INT_MAX) return -1;
t = max(t, distance[i]);
}

return t;
}
};

//SPFA:
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<vector<int>>> graph(n+1);

for (auto &time : times)
graph[time[0]].push_back({time[1], time[2]}); //{node, edge_len}

vector<int> path(n+1, INT_MAX);
queue<pair<int,int>> q; //{path_len, node}

q.push({0, k});

while (!q.empty()) {
auto p = q.front(); q.pop();

if (p.first >= path[p.second]) continue;

path[p.second] = p.first;

for (auto &edge : graph[p.second])
q.push({p.first + edge[1], edge[0]});
}

int ans = INT_MIN;

for (int i = 1; i < (int)path.size(); i++) {
if (path[i] == INT_MAX) return -1;
ans = max(ans, path[i]);
}

return ans;
}
};