The problem
A signal starts at node k in a directed weighted graph of n nodes. times[i] = (u, v, w) means the signal takes w to travel u → v. Return the time for ALL nodes to receive it, or −1 if some node never does.
Stuck? Reveal hints one at a time
How to approach it
- 1Build an adjacency list u → [(v, w)].
- 2Run Dijkstra from k: a min-heap of (distance, node), popping the closest unsettled node each round.
- 3Skip stale heap entries (popped distance greater than the recorded best).
- 4Relax each outgoing edge; push improved distances.
- 5Answer = max recorded distance, or −1 if any node was never reached.
Key insight
The signal reaches everyone when the LAST node hears it — so you want the maximum of the minimum arrival times, exactly what Dijkstra hands you.
The solution
Watch out for
- Forgetting the stale-entry check makes Dijkstra quadratic on dense re-pushes.
- Nodes are 1-indexed; count reached nodes against n, not the adjacency list size.