TSP with Bitmask DP

Problem

Given a symmetric distance matrix dist for n cities, return the minimum cost of a tour that starts at city 0, visits every city exactly once and returns to 0.

Use bitmask DP: dp[mask][u] is the cheapest path visiting the cities in mask and ending at u, then close the tour back to 0. A single city costs 0.

Hint

Mask 1 starts at city 0 for free, and the answer closes each full-mask state back to city 0.

Test cases

case 1

in: [[[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]]

expected: 80

case 2

in: [[[0,1,2],[1,0,1],[2,1,0]]]

expected: 4

case 3

in: [[[0]]]

expected: 0

case 4

in: [[[0,5],[5,0]]]

expected: 10

case 5

in: [[[0,1,1],[1,0,1],[1,1,0]]]

expected: 3

Starter codePython

def tsp_bitmask(dist):
    # Your code here
    pass

5 test cases · run your code against them in the editor