1349. Minimum Cost to Visit Every Node (Bitmask TSP)

Given an n x n cost matrix where cost[i][j] is the price of travelling directly from node i to node j, start at node 0 and visit every node exactly once. Return the minimum total travel cost of such a path. The path does not return to the start.

Input: A JSON object {"cost": [[...], ...]} representing an n x n matrix.

Output: Return the minimum cost of a Hamiltonian path starting at node 0.

Examples

Input: {"cost":[[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]}
Output: 65
Explanation: The cheapest visiting order from node 0 costs 65.

Input: {"cost":[[0,5,9],[5,0,3],[9,3,0]]}
Output: 8
Explanation: Visiting 0 then 1 then 2 costs 8.

Constraints

• 1 <= n <= 12
• 0 <= cost[i][j] <= 10^5
• cost[i][i] = 0

Asked by