Loading...
Loading...
Loading...
A driver must visit N depots, starting at depot 0, visiting every depot exactly once and then returning to depot 0. D[i][j] is the distance from depot i to depot j, and it may differ from D[j][i]. Print the smallest total distance of such a round trip.
Example
Input
4 0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0
Output
80
The route 0, 1, 3, 2, 0 costs 10 + 25 + 30 + 15.
Try the problem first. Open one hint at a time.
The state is the set of visited depots and the depot you stand in. dp[mask][last] is the shortest way so far.
Start with only depot 0 visited. At the end, add the way home from every possible last depot.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor