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 <= 1001 <= times.length <= 6000times[i].length == 31 <= ui, vi <= nui != vi0 <= wi <= 100- All the pairs
(ui, vi)are unique. (i.e., no multiple edges.)
Solution:
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 int networkDelayTime(int[][] times, int n, int k) {
Map<Integer, List<int[]>> graph = new HashMap<>();
for (int i = 1; i <= n; i++) {
graph.put(i, new ArrayList<>());
}
for (int[] t : times) {
graph.get(t[0]).add(new int[]{t[1], t[2]});
}
Queue<int[]> q = new PriorityQueue<>((a, b) -> a[1] - b[1]);
q.add(new int[]{k, 0});
Map<Integer, Integer> res = new HashMap<>();
while (q.size() != 0) {
int[] cur = q.poll();
if (res.containsKey(cur[0])) {
continue;
}
//We try to add the same element to the queue.
//But only the cur[1] having minimum value will be considered because
//of the above containsKey condition.
res.put(cur[0], cur[1]);
for (int i[] : graph.get(cur[0])) {
q.add(new int[]{i[0], cur[1] + i[1]});
}
}
if (res.size() != n) {
return -1;
}
int time = 0;
for (int t : res.values()) {
time = Math.max(time, t);
}
return time;
}
}
