The problem
The lines form a directed acyclic graph (a DAG): following lines, you can never come back to a station. Times can be negative. Return a pair of lists (dist, ways). dist[v] is the least total time from s to v, or None if v cannot be reached. ways[v] is how many different routes from s to v take exactly that time, as the remainder after dividing by 1,000,000,007 (0 if v cannot be reached). Two routes are different if they use a different line at any point, so a line listed twice gives two routes.
dag_routes(4, [(0, 1, 1), (0, 2, 1), (1, 3, 1),
(2, 3, 1), (0, 3, 3)], 0)
# ([0, 1, 1, 2], [1, 1, 1, 2])
Limits
- Up to 100,000 stations and about 250,000 lines.
- Routes can be 100,000 lines long, so recursion is too deep. Aim for O(V + E). The big tests have 4 seconds each.
Builds on PATH-6 Shortest paths in DAGs.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | Refunds | Not run | |
| 3 | Stations before the start | Not run | |
| 4 | Ties count together | Not run | |
| 5 | A cheaper way replaces the count | Not run | |
| 6 | A line given twice | Not run | |
| 7 | 40 layers of two | Not run | |
| 8 | A chain of 100,000, listed backwards | Not run | |
| 9 | 100,000 stations, 250,000 lines | Not run |