Given n network nodes and edges (u,v,w), find the time for all nodes to receive signal sent from node k. Return -1 if not all nodes can receive the signal.
Input: times=[[2,1,1],[2,3,1],[3,4,1]], n=4, k=2 → Output: 2Input: times=[[1,2,1]], n=2, k=1 → Output: 1
Dijkstra from node k. The answer is the maximum shortest distance among all reachable nodes.
- Build adjacency list. Run Dijkstra from k.
- dist[] tracks shortest time to each node.
- After Dijkstra, find max(dist[]). If any node is unreachable (INF), return -1.
import java.util.*;
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
Map<Integer,List<int[]>> graph = new HashMap<>();
for (int[] t : times) graph.computeIfAbsent(t[0], x->new ArrayList<>()).add(new int[]{t[1],t[2]});
int[] dist = new int[n+1]; Arrays.fill(dist, Integer.MAX_VALUE); dist[k] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[1]-b[1]);
pq.offer(new int[]{k,0});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
if (cur[1] > dist[cur[0]]) continue;
for (int[] nb : graph.getOrDefault(cur[0], Collections.emptyList())) {
int newDist = dist[cur[0]] + nb[1];
if (newDist < dist[nb[0]]) { dist[nb[0]] = newDist; pq.offer(new int[]{nb[0],newDist}); }
}
}
int max = 0;
for (int i = 1; i <= n; i++) { if (dist[i] == Integer.MAX_VALUE) return -1; max = Math.max(max, dist[i]); }
return max;
}
}
- Time Complexity: O((V+E) log V)
- Space Complexity: O(V+E)