1108. Travelling Salesman Problem (Bitmask DP)

Given n cities and an n x n symmetric distance matrix dist, return the minimum cost of a tour that starts at city 0, visits every city exactly once, and returns to city 0 (the classic TSP via Held-Karp). The input is JSON {n, dist}.

Input: JSON {n, dist}.

Output: Integer — the minimum tour cost.

Examples

Input: {"n":4,"dist":[[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]}
Output: 80
Explanation: Optimal tour costs 80.

Input: {"n":1,"dist":[[0]]}
Output: 0
Explanation: No travel needed.

Input: {"n":2,"dist":[[0,5],[5,0]]}
Output: 10
Explanation: Go and return.

Constraints

• 1<=n<=15

Asked by