Network Delay Time

Problem

A network has n nodes labeled 1..n. You are given a list times of directed links, where times[i] = [u, v, w] means a signal sent from u reaches v after w time units. A signal is broadcast from node k at time 0 and is forwarded along every outgoing link the moment it arrives at a node.

Return the earliest time at which every node has received the signal. If some node can never receive it, return -1.

• Up to a couple hundred nodes, and k is one of them.
• Up to several thousand directed links.
• Link delays are positive and fit comfortably in a small int; a link never points from a node to itself.
• There are no duplicate (u, v) links.

Examples

• times = [[3,1,2],[3,2,2],[2,4,3]], n = 4, k = 3 → 5. Nodes 1 and 2 hear it at time 2; node 4 hears it via 2 at time 5.
• times = [[2,1,3]], n = 2, k = 2 → 3. Single link, both nodes covered.
• times = [[2,1,3]], n = 2, k = 1 → -1. The link points the wrong way, so node 2 is unreachable from 1.

Hints

1. The answer is the largest of the shortest-path distances from k. Which classic algorithm gives single-source shortest paths with non-negative weights?
2. A plain BFS does not work because links have different weights. What ordering should you explore nodes in instead?
3. Dijkstra with a min-heap keyed by tentative distance; the answer is the max finalized distance, or -1 if any node is never popped.