The problem
A railway has n stations joined by a spanning tree of lines: tree holds n − 1 lines (u, v, w), each costing w a year to run, and together they join every station with no loop. A new line extra = (a, b, w) is offered. Using the old lines and the new one, which lines should run to join every station as cheaply as possible? Return the total yearly cost of that cheapest spanning tree.
tree = [(0, 1, 4), (1, 2, 2), (1, 3, 7), (3, 4, 1)]
cheaper_tree(5, tree, (2, 3, 3)) # 10
cheaper_tree(5, tree, (0, 4, 9)) # 14
In the first call, the new line closes the loop 2 → 1 → 3 → 2. Dropping the line 1–3, which costs 7, gives 14 − 7 + 3 = 10. Costs are whole numbers and may be negative. The new line may join a station to itself, or two stations already joined by a line.
Limits
- Up to 100,000 stations.
- The tree can be a path 100,000 stations long, so a recursive search is too deep. The big tests have 3 seconds each.
Builds on SPAN-1 Spanning trees.
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 | The new line is too expensive | Not run | |
| 3 | The most expensive line is elsewhere | Not run | |
| 4 | Exactly as expensive | Not run | |
| 5 | A line from a station to itself | Not run | |
| 6 | Beside a tree line | Not run | |
| 7 | Negative costs | Not run | |
| 8 | One station | Not run | |
| 9 | A path of 100,000 | Not run | |
| 10 | A random tree of 100,000 | Not run | |
| 11 | Many lines at the same cost | Not run |