756. Second Fastest Arrival
A tram line has n stations numbered 1 to n, joined by two-way tracks edges[i] = [u, v]. The network is connected, with no duplicate tracks and no self-loops. Riding one track always takes time minutes. Every station has a signal, and all signals switch together between green and red every change minutes, starting green at minute 0. A tram may depart only while the signal is green; if it is already green it departs at once, otherwise it waits for the next green.
A tram leaves station 1 at minute 0 and may revisit stations and tracks. Among all possible arrival times at station n, return the second smallest value, meaning the smallest time strictly larger than the fastest arrival time.
Example 1
- Input:
- n = 5edges = [[1,2],[1,3],[3,4],[4,5]]time = 3change = 5
- Output:
- 23
- Explanation:
The fastest trip 1-3-4-5 arrives at minute 13; a tree has no walks of even length to station 5, so the next candidate has 5 tracks (for example 1-3-4-5-4-5) and arrives at minute 23 after waiting at red lights.
Example 2
- Input:
- n = 2edges = [[1,2]]time = 3change = 2
- Output:
- 11
- Explanation:
With a single track the second arrival uses it three times (1-2-1-2): depart at 0, wait from 3 until 4 at red, depart at 4, arrive at 7, wait until 8 and arrive at minute 11.
Example 3
- Input:
- n = 3edges = [[1,2],[2,3],[1,3]]time = 2change = 10
- Output:
- 4
- Explanation:
The direct track arrives at minute 2; the next distinct time comes from the two-track route 1-2-3 arriving at minute 4, all within the first green phase.
Constraints
- 2 ≤ n ≤ 104
- n - 1 ≤ edges.length ≤ min(2 * 104, n * (n - 1) / 2)
- 1 ≤ u, v ≤ n, u ≠ v, and the graph is connected
- 1 ≤ time, change ≤ 103
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)
- Space
- O(n + m)