PreviousNext
Coding/Dynamic programming

Traveling salesman open path

Write codeHard40 minDoorDash and Uber style

Your task

Given a symmetric n x n distance matrix (dist[i][j] >= 0, dist[i][i] = 0), a delivery driver starts at city 0 and must visit every city exactly once (an open Hamiltonian path, no return to 0). Return the minimum total travel distance. n is small (n <= 12). The matrix has at least one city.

Examples

tsp_min_path(dist: list[list[int]]) -> int
Example 1
Inputtsp_min_path([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])
Output65