Visit Every Station
HardGraphs
Problem
A maintenance crew must inspect all n stations of a small rail network, numbered 0 to n - 1. Each [a, b] in edges is a two-way track, and the network is connected.
The crew may start and finish at any station, and may pass through stations and tracks more than once. Return the minimum number of tracks travelled so that every station has been visited at least once.
Example 1
- Input:
- n = 4, edges = [[0,1],[0,2],[0,3]]
- Output:
- 4
One best tour is 1 → 0 → 2 → 0 → 3: four tracks.
Example 2
- Input:
- n = 4, edges = [[0,1],[1,2],[2,3]]
- Output:
- 3
Start at one end of the line and walk to the other.
Constraints
- 1 ≤ n ≤ 12
- 0 ≤ edges.length ≤ n(n-1)/2
- The network is connected; no duplicate tracks.
Hint
Show the first hint
Being at a station is not enough information: you also need to know which stations you have already visited.
Walkthrough
How to approach it
01Clarify before coding
- Can stations and tracks be reused? Yes; this is a walk, not a simple path.
- Do start and end have to be the same? No, both are free.
- How small is n? At most 12, a strong hint that exponential state in n is acceptable.
02Brute force
Try every order of visiting the stations, connecting consecutive ones by their shortest distance, and keep the cheapest.
Cost: n! orders: 479 million permutations for n = 12, each costing O(n).
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.