-
Notifications
You must be signed in to change notification settings - Fork 2
/
NetworkDelayTime.java
85 lines (74 loc) · 2.4 KB
/
NetworkDelayTime.java
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
package Leetcode;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
/**
* @author kalpak
*
* 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.)
*
*/
public class NetworkDelayTime {
public static int networkDelayTime(int[][] times, int n, int k) {
Map<Integer, Map<Integer,Integer>> map = new HashMap<>();
int result = 0;
boolean[] isVisited = new boolean[n + 1];
for(int[] time : times){
map.putIfAbsent(time[0], new HashMap<>());
map.get(time[0]).put(time[1], time[2]);
}
//distance, node into minHeap
Queue<int[]> minHeap = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
minHeap.add(new int[]{0, k});
while (!minHeap.isEmpty()) {
int[] current = minHeap.remove();
int currentNode = current[1];
int currentTime = current[0];
if(isVisited[currentNode])
continue;
isVisited[currentNode] = true;
result = currentTime;
n--;
if(map.containsKey(currentNode)){
for(int next : map.get(currentNode).keySet()){
minHeap.add(new int[]{currentTime + map.get(currentNode).get(next), next});
}
}
}
return n == 0 ? result : -1;
}
public static void main(String[] args) {
int[][] times = new int[][]{{2,1,1},{2,3,1},{3,4,1}};
System.out.println("The network Delay time is : " + networkDelayTime(times, 4, 2));
}
}