Traveling Salesman Problem with Bitmask Dynamic Programming

This problem requires you to solve the Traveling Salesman Problem (TSP) using dynamic programming combined with bitmasking. Given a complete directed weighted graph, find a Hamiltonian cycle that starts and ends at vertex 0 and minimizes the total travel cost. In other words, if the cities are labeled 0, 1, ..., n-1, you need to find the minimum cost path that starts at city 0, visits every other city exactly once, and returns to city 0.

The problem can be mathematically formulated as follows:

Find the minimum value of

$$\min_{\text{permutation } \pi} \left( d(0,\pi(1)) + \sum_{i=1}^{n-2} d(\pi(i), \pi(i+1)) + d(\pi(n-1), 0) \right) $$

where \(d(i,j)\) is the distance from city i to city j.

inputFormat

The input is given via standard input (stdin) and is structured as follows:

• The first line contains an integer n (the number of cities).
• The next n lines each contain n space-separated integers, where the j-th integer in the i-th line represents the distance from city i to city j.

You may assume that the distance from a city to itself is 0.

outputFormat

Output a single integer via standard output (stdout) representing the minimum possible total distance to complete the cycle.

## sample

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

80