1226. Minimum Cost to Visit Every Node

Given a symmetric distance matrix dist, start at node 0 and visit every node exactly once. Unlike the classic tour, you do not return to the start. Return the minimum total travel cost. The input is JSON {dist}.

Input: JSON {dist}.

Output: Integer — the minimum cost of an open path visiting all nodes.

Examples

Input: {"dist":[[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]}
Output: 65
Explanation: An open path visiting all nodes costs 65.

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

Input: {"dist":[[0,7],[7,0]]}
Output: 7
Explanation: One edge, no return.

Constraints

• 1<=n<=15

Asked by