Travelling Salesman (Small)
Mastery
dist[i][j] is the distance from city i to city j (it may differ from dist[j][i]). Starting at city 0, visit every city exactly once and come back to city 0. Return the shortest total distance. With one city the answer is 0.
For [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]] the answer is 80.
The starter code tries every order of the cities. It is correct but too slow for more than 9 or 10 cities.
Examples
Example 1
Input:
tsp([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])
Output:
80
Example 2
Input:
tsp([[0, 5], [7, 0]])
Output:
12
Constraints
0 <= number of cities <= 131 <= dist[i][j] <= 100fori != j
Theory
Go to TheoryKeywords
dsa-sheetdynamic-programmingintervals-and-states
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.