Traveling Salesman Problem

You are given several test cases. In each test case, you are given an integer \(N\) representing the number of cities and an \(N \times N\) matrix \(D\) where \(D[i][j]\) is the distance from city \(i\) to city \(j\). Your task is to determine the minimum possible total distance of a route that starts at city 0, visits every city exactly once, and returns to city 0. This problem can be solved using dynamic programming with bit masking. The state transitions typically involve considering all subsets of visited cities, where the number of states is \(O(N \cdot 2^N)\).

Input Format: The first line of input contains an integer representing the number of test cases. For each test case, the first line contains the integer \(N\). This is followed by \(N\) lines each containing \(N\) space-separated integers representing the distance matrix.

Output Format: For each test case, output a single line containing the minimum route cost.

inputFormat

The input begins with an integer \(T\), the number of test cases. For each test case, the following input is provided:

• An integer \(N\) representing the number of cities.
• \(N\) lines, each containing \(N\) space-separated integers, where the \(j\)-th integer in the \(i\)-th line denotes the distance from city \(i\) to city \(j\).

All input is read from standard input (stdin).

outputFormat

For each test case, output one line containing the minimum total distance of the route that starts and ends at city 0, while visiting every city exactly once. The answers for all test cases should be printed in order to standard output (stdout), each on a separate line.

## sample

1
2
0 1
1 0

2

</p>