Timetable Earliest Arrival
MediumAdvanced Graphs
Problem
A rail network has n stations. Each lines[i] = [u, v, first, period, duration] is a one-way service from u to v: trains leave u at times first, first + period, first + 2·period, … and each trip takes duration minutes.
A passenger is at station 0 at time 0 and may wait at any station. Return the earliest time at which they can arrive at station n - 1, or -1 if it is unreachable.
Example 1
- Input:
- n = 3, lines = [[0,1,0,5,3],[1,2,4,10,2],[0,2,20,100,1]]
- Output:
- 6
Take the time-0 train to station 1 (arrive 3), wait for the time-4 train, arrive at station 2 at 6. The direct train only leaves at 20.
Example 2
- Input:
- n = 2, lines = [[0,1,7,10,1]]
- Output:
- 8
Example 3
- Input:
- n = 3, lines = [[0,1,0,1,1]]
- Output:
- -1
Constraints
- 1 ≤ n ≤ 10^4
- 0 ≤ lines.length ≤ 2·10^4
- 0 ≤ first ≤ 10^6
- 1 ≤ period, duration ≤ 10^6
Hint
Show the first hint
The cost of a line depends on when you reach its start. Does arriving earlier ever hurt?
Walkthrough
How to approach it
01Clarify before coding
- Can the passenger wait? Yes, any amount of time at any station.
- Can a train be boarded at exactly the moment you arrive? Yes, departure time ≥ arrival time.
- Station 0 is also the destination when n = 1? Then the answer is 0.
02Brute force
Simulate minute by minute which stations are reachable by time t until the destination appears.
Cost: Proportional to the answer (up to ~10^9 minutes) times the number of lines: hopeless.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.