781. Signal Spread Time
A telemetry mesh has n relay stations numbered from 1 to n. Each entry times[i] = [u, v, w] is a one-way cable: a pulse that reaches station u arrives at station v exactly w milliseconds later. Every station forwards the pulse down all of its outgoing cables the instant it first receives it.
A pulse is injected at station k at time 0. Return the time at which the last station receives it, that is, the largest of the earliest arrival times over all stations. If at least one station can never be reached, return -1. Cables may share endpoints, may form loops, and a cable may take 0 ms.
Example 1
- Input:
- times = [[3,1,2],[3,2,1],[2,4,2]], n = 4, k = 3
- Output:
- 3
- Explanation:
Station 3 reaches station 2 after 1 ms and station 1 after 2 ms, and station 4 follows station 2 after 2 more ms, so the last station hears the pulse at time 3.
Example 2
- Input:
- times = [[1,2,3]], n = 3, k = 1
- Output:
- -1
- Explanation:
Station 3 has no incoming cable from anything reachable, so it never receives the pulse and the answer is -1.
Example 3
- Input:
- times = [[1,2,4],[1,3,1],[3,2,2],[2,4,0]], n = 4, k = 1
- Output:
- 3
- Explanation:
Station 2 is reached faster through station 3 (1 + 2 = 3 ms) than directly (4 ms), and station 4 follows over a 0 ms cable, so the last arrival is at time 3.
Constraints
- 1 ≤ k ≤ n ≤ 105
- 0 ≤ times.length ≤ 2 * 105
- times[i] = [u, v, w] with 1 ≤ u, v ≤ n and 0 ≤ w ≤ 100
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O((n + m) log n)
- Space
- O(n + m)