Traveling Salesman (Bitmask DP)

Given a complete distance matrix dist of size n x n (0-indexed), find the minimum tour cost that starts at node 0, visits every node exactly once, and returns to node 0.

Function signature

func TSPMinTourCost(dist [][]int) int

Example

dist = [
  [0,10,15,20],
  [10,0,35,25],
  [15,35,0,30],
  [20,25,30,0]
]
output = 80

Constraints

• 1 <= n <= 15
• 0 <= dist[i][j] <= 1_000_000

Notes

• Use bitmask DP in O(n^2 * 2^n).