295. Network Delay Time

"When does the signal reach every node?" is the maximum of the shortest paths from k to all others. Dijkstra computes all those distances in one pass.

Approach

1. Build adjacency u -> [(v, w), …].
2. Min-heap seeded with (0, k). Popped distances are final.
3. Answer = max of final distances; return -1 if any node is unreachable.

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[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        heap.offer(new int[]{0, k});
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int d = top[0], u = top[1];
            if (d > dist[u]) continue;
            if (graph.containsKey(u)) {
                for (int[] edge : graph.get(u)) {
                    int v = edge[0], w = edge[1];
                    int nd = d + w;
                    if (nd < dist[v]) {
                        dist[v] = nd;
                        heap.offer(new int[]{nd, v});
                    }
                }
            }
        }
        int worst = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            worst = Math.max(worst, dist[i]);
        }
        return worst;
    }
}