Traveling Salesman Problem (TSP) with Dynamic Programming

You are given a complete directed graph with n vertices. The cost of traveling from vertex i to vertex j is given by a matrix d where the element d_i,j represents the cost. Your task is to determine the minimum cost of a circular tour that starts at vertex 0, visits each vertex exactly once, and returns to the starting vertex.

The problem can be formulated as:

$$\min_{\pi \in S_{n-1}} \Bigl( d_{0,\pi(0)} + \sum_{i=0}^{n-2} d_{\pi(i),\pi(i+1)} + d_{\pi(n-1),0} \Bigr) $$

Implement a solution using dynamic programming with bitmasking.

inputFormat

The input is given via standard input. The first line contains an integer n representing the number of cities. Each of the following n lines contains n space-separated integers, where the jth integer on the ith line represents the cost d_i,j of traveling from city i to city j.

outputFormat

Output a single integer on standard output representing the minimum total cost of the circular tour.

## sample

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

80