Description
Given an n x n symmetric weight matrix (matrix[i][i] = 0), return the minimum total weight of a Hamiltonian cycle that starts and ends at vertex 0 and visits each other vertex exactly once.
Examples
Input:
matrix = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]Output:
80Explanation:
The classic 4-city TSP example admits an optimal cycle of total weight 80.
Input:
matrix = [[0]]Output:
0Explanation:
A graph with one vertex has the trivial cycle of length 0.
Input:
matrix = [[0,1,1],[1,0,1],[1,1,0]]Output:
3Explanation:
Any Hamiltonian cycle on the unit triangle traverses three edges of weight 1, for a total of 3.
Constraints
- •
1 ≤ n ≤ 12 - •
0 ≤ matrix[i][j] ≤ 10⁴