PreviousNext
Coding/Dynamic programming

Traveling salesman

Write codeHard35 minAmazon style

Your task

Given a complete directed graph as an n x n distance matrix dist (dist[i][j] is the cost from city i to city j, dist[i][i]=0), find the minimum cost of a tour that starts at city 0, visits every city exactly once, and returns to city 0 (closed Traveling Salesman). Return that minimum cost. Constraints: 1 <= n <= 13, 0 <= dist[i][j] <= 10000.

Examples

tsp_min_tour(dist: list[list[int]]) -> int
Example 1
Inputtsp_min_tour([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])
Output80