1225. Travelling Salesman Problem (TSP)

Given a symmetric distance matrix dist where dist[i][j] is the cost between cities i and j, start at city 0, visit every city exactly once, and return to city 0. Return the minimum total tour cost. The input is JSON {dist}.

Input: JSON {dist}.

Output: Integer — the minimum tour cost.

Examples

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

Input: {"dist":[[0]]}
Output: 0
Explanation: Single city.

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

Constraints

• 1<=n<=15

Asked by