Network Delay Time
MediumGraphs
A network has n nodes labelled 1 to n. Each entry times[i] = [u, v, w] is a directed link: a signal at node u reaches node v after w units of time.
A signal is sent from node k at time 0 and spreads along every link simultaneously, so each node receives it at the earliest time any path from k can deliver it. Return the time at which the last node receives the signal, or -1 if some node can never receive it.
Example 1
- Input:
- times = [[1, 2, 10], [1, 3, 1], [3, 2, 1]], n = 3, k = 1
- Output:
- 2
- Explanation
- Node 3 is reached directly at time 1. Node 2 can be reached directly at time 10, but going through node 3 arrives at time 2, which is sooner. The last arrival is therefore at time 2.
Example 2
- Input:
- times = [[1, 2, 3], [3, 2, 1]], n = 3, k = 1
- Output:
- -1
- Explanation
- Node 2 is reached at time 3, but no link leads into node 3 from a node the signal can reach, so node 3 never receives it.
Example 3
- Input:
- times = [[1, 2, 1], [2, 1, 1], [2, 3, 4]], n = 3, k = 1
- Output:
- 5
- Explanation
- Node 2 is reached at time 1, then node 3 at time 1 + 4 = 5. The slowest arrival is 5.
Constraints
1 <= k <= n <= 1000 <= times.length <= 6000times[i].length == 31 <= u, v <= nandu != v0 <= w <= 100- All pairs
(u, v)are distinct