743. Network Delay Time

A network has n nodes labeled 1..n and directed travel times times[i] = [u, v, w]. A signal is sent from node k. Return the time until all nodes receive it, or -1 if some never do.

Always settle the closest unsettled node next; its distance is final because all weights are non-negative. Then relax its outgoing edges. The answer is the largest settled distance.

1function networkDelayTime(times: number[][], n: number, k: number): number {
2  const adj = new Map<number, [number, number][]>();
3  for (const [u, v, w] of times) (adj.get(u) ?? adj.set(u, []).get(u)!).push([v, w]);
4  const dist = new Map<number, number>(), heap = new MinPriorityQueue<[number, number]>((e) => e[0]);
5  heap.enqueue([0, k]);
6  while (heap.size()) {
7    const [d, u] = heap.dequeue();
8    if (dist.has(u)) continue;
9    dist.set(u, d);
10    for (const [v, w] of adj.get(u) ?? []) if (!dist.has(v)) heap.enqueue([d + w, v]);
11  }
12  return dist.size === n ? Math.max(...dist.values()) : -1;
13}

network (u → v)

settled dist

∞

min-heap (dist, node)

0, 2

Push (0, 2).

1 / 0

Space: play/pause · ←/→: step