Traveling Salesman Problem with Bitmask DP

This problem requires you to solve the classic Traveling Salesman Problem (TSP) using dynamic programming with bitmasking. Given a cost matrix representing the cost between each pair of cities, your task is to determine the minimum cost of a Hamiltonian cycle that starts and ends at city 0. If no such cycle exists, output -1.

The solution involves maintaining a DP table where each state is represented by a bitmask indicating the set of visited cities and the last visited city. The transition involves updating the state by considering unvisited cities and adding the corresponding travel cost. Finally, complete the cycle by returning to the starting city.

Note: Input is read from standard input and output is printed to standard output.

inputFormat

The input begins with a single integer T, denoting the number of test cases. Each test case starts with an integer n, representing the number of cities. The following n lines each contain n space-separated integers where the j-th integer in the i-th line represents the cost of traveling from city i to city j.

Example:

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

outputFormat

For each test case, output a single line containing the minimum cost of a Hamiltonian cycle that visits every city exactly once and returns to the starting city. If such a cycle cannot be found, print -1.

Example output for the above test cases:

80
60
4

## sample

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

80
60
4

</p>