1372. Travelling Salesman — Classic Bitmask DP

Given an n x n matrix where cost[i][j] is the price of travelling directly from city i to city j, start at city 0, visit every other city exactly once, and return to city 0. Return the minimum total cost of such a tour.

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

Output: Return the minimum cost of a tour that starts and ends at city 0.

Examples

Input: {"cost":[[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]}
Output: 80
Explanation: The cheapest round tour from city 0 costs 80.

Input: {"cost":[[0]]}
Output: 0
Explanation: With one city there is nothing to travel -> 0.

Constraints

• 1 <= n <= 15
• 0 <= cost[i][j] <= 10^6
• cost[i][i] = 0

Asked by