PreviousNext
Coding/Dynamic programming

Shortest Hamiltonian path

Write codeHard35 minUber and DoorDash style

Your task

Given a symmetric distance matrix dist for N nodes (dist[i][j] is the edge length), find the length of the shortest Hamiltonian path that visits every node exactly once. The path may start and end at any node (it is an open path, not a cycle). N is small (up to ~13). Return the minimum total length.

Examples

shortest_hamiltonian_path(dist: list[list[int]]) -> int
Example 1
Inputshortest_hamiltonian_path([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])
Output50