The problem
Some tickets in this network come with a refund, so a fare (u, v, w) can have a negative w. Return a list with one entry per station: the cheapest total fare from station s; None if the station cannot be reached; or -math.inf if the fare can be made lower and lower without end, because a route to it can use a loop whose fares add up to less than 0.
cheapest(5, [(0, 1, 4), (0, 2, 2), (2, 1, -1),
(1, 3, 3), (2, 3, 6), (3, 4, -2)], 0)
# [0, 1, 2, 4, 2]
cheapest(5, [(0, 1, 1), (1, 2, -1), (2, 1, -1),
(2, 3, 4)], 0)
# [0, -inf, -inf, -inf, None]
The second network has the loop 1 → 2 → 1, which costs −2 each time round. The tests show -math.inf as '-inf'. Fares are whole numbers.
Limits
- Up to 1,000 stations and 4,002 fares.
- Bellman–Ford is O(V · E), about 4 million steps here. Stop early when a round changes nothing. The big tests have 6 seconds each.
Builds on PATH-4 Bellman-Ford.
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 | Dijkstra's method is wrong here | Not run | |
| 3 | Stations that cannot be reached | Not run | |
| 4 | A loop of refunds | Not run | |
| 5 | A loop of refunds that cannot be reached | Not run | |
| 6 | A cheap way that a loop beats later | Not run | |
| 7 | The start is on the loop | Not run | |
| 8 | A loop that costs exactly 0 | Not run | |
| 9 | 1,000 stations, 3,000 fares and a chain | Not run | |
| 10 | The same with a loop of refunds | Not run |