Network Delay Time
There are N
network nodes, labelled 1
to N
.
Given times
, a list of travel times as directed edges times[i] = (u, v, w)
, where u
is the source node, v
is the target node, and w
is the time it takes for a signal to travel from source to target.
Now, we send a signal from a certain node K
. How long will it take for all nodes to receive the signal? If it is impossible, return -1
.
Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2
Note:
N
will be in the range[1, 100]
.K
will be in the range[1, N]
.The length of
times
will be in the range[1, 6000]
.All edges
times[i] = (u, v, w)
will have1 <= u, v <= N
and0 <= w <= 100
.
class Solution {
public int networkDelayTime(int[][] times, int N, int K) {
// Creating Adjacency List
ArrayList<int[]>[] graph = new ArrayList[N];
for (int i = 0; i < N; i++)
graph[i] = new ArrayList<>();
for (int[] edge : times)
graph[edge[0] - 1].add(new int[] { edge[1] - 1, edge[2] });
// (distance, node) into pq
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
pq.add(new int[] { 0, K - 1 });
boolean[] visited = new boolean[N];
int res = 0, coveredNodes = 0;
while (!pq.isEmpty()) {
// Picking the Node at shortest Distance
int[] cur = pq.remove();
int curDist = cur[0];
int curNode = cur[1];
if (visited[curNode])
continue;
visited[curNode] = true;
// The last node in the PQ will have the largest distance already
res = curDist;
coveredNodes++;
for (int[] node : graph[curNode])
pq.add(new int[] { curDist + node[1], node[0] });
}
return coveredNodes == N ? res : -1;
}
}
Last updated