Taco: Minimum Tour Distance

You are given a set of cities and a distance matrix representing the distance between every pair of cities. Your task is to compute the minimum tour distance required to visit every city exactly once and return to the starting city. This is a classic Traveling Salesman Problem (TSP) which can be formulated as:

\( \min_{\pi}\ \left(d(\pi(0),\pi(1)) + d(\pi(1),\pi(2)) + \cdots + d(\pi(n-1),\pi(0))\right) \)

where \( d(i,j) \) is the distance from city \( i \) to city \( j \), and \( \pi \) is a permutation of the cities. Each city must be visited exactly once before returning to the first city.

inputFormat

The input starts with an integer \( n \) denoting the number of cities. The following \( n \) lines each contain \( n \) space-separated integers. The \( j \)-th integer on the \( i \)-th line is the distance \( d(i, j) \) between city \( i \) and city \( j \).

outputFormat

Output a single integer which is the minimum tour distance. This value is the minimum total distance required to start from the first city, visit every other city exactly once, and return to the starting city.

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

80