489. Network Delay Time
A network has n nodes labeled 1 through n, connected by one-way links. You are given the link list times, where times[i] = [u, v, w] means a signal leaving node u arrives at node v exactly w time units later, along with n and a starting node k.
At time 0 node k broadcasts a signal. Whenever a node receives the signal, it instantly rebroadcasts it down all of its outgoing links. Return the earliest moment at which every node has heard the signal. If some node can never hear it, return -1.
In other words: compute the shortest travel time from k to every other node, and report the largest of those times.
Example 1:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Explanation: Node 2 broadcasts at t = 0. Nodes 1 and 3 hear it at t = 1; node 3 relays it to node 4, which hears it at t = 2. The slowest node sets the answer: 2.
Example 2:
Input: times = [[1,2,5]], n = 3, k = 1
Output: -1
Explanation: Node 3 has no incoming path from node 1, so it never hears the signal.
Constraints:
- 1 ≤ k ≤ n ≤ 100
- 0 ≤ m ≤ 6000
- 1 ≤ u, v ≤ n and u ≠ v
- 1 ≤ w ≤ 100
- The link list may contain several links between the same pair of nodes.
Hints:
"Earliest time every node hears it" is just the largest shortest-path distance from k. If any node's distance stays infinite, return -1.
All weights are positive, so Dijkstra applies: repeatedly settle the unvisited node with the smallest known distance and relax its outgoing edges. A min-heap keyed by distance does the ordering for you.
Push updated distances into the heap without deleting old entries — when you pop a pair whose distance is worse than the recorded one, it is stale; skip it.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Expected output: 2