A network has n nodes, numbered from 1 to n. Each entry [u, v, w] in times is a one-way
link: a signal at node u reaches node v after w minutes.
A signal starts at node k at minute 0 and travels along every link at once. Return the number
of minutes until every node has received it, or -1 if some node can never be reached.
Example 1
- Input
- times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]], n = 4, k = 1
- Output
- 4
Example 2
- Input
- times = [[1, 2, 5], [1, 3, 2]], n = 3, k = 2
- Output
- -1
Constraints
- 1 ≤
k≤n≤ 500 timesholds 0 to 6000 links. In each,uandvare different nodes from 1 ton, and no (u,v) pair appears twice.- 0 ≤
w≤ 100
Show the pattern
Shortest paths
The signal reaches each node along its quickest route, and no delay is negative. Dijkstra's algorithm with a heap finds every quickest arrival time; the answer is the latest of them.
See shortest paths in a visualiserShow the approach
Build a list of outgoing links for each node. Then run Dijkstra's algorithm from k: a min-heap
holds (arrival time, node) pairs, starting with (0, k). Pop the earliest pair. If its node
already has a time, skip it, because a quicker route got there first. Otherwise record the time,
and push every neighbour v that has no time yet with time + w.
Because no delay is negative, the first time a node comes off the heap is its quickest arrival.
If every node gets a time, the answer is the largest of them; otherwise it is -1.
Time: O(E log E) for E links · Space: O(n + E)