Traveling Salesman Problem: Minimum Tour Distance

You are given a complete weighted graph of n cities represented by an n x n distance matrix. The task is to determine the minimum possible distance to travel through all cities exactly once and return to the starting city. This is a classic Traveling Salesman Problem (TSP) formulation.

The distance between city i and city j is given by an integer and obeys the properties of a complete graph. The solution must consider all possible permutations of city visits to determine the route with the least total distance.

Note: Since the number of cities is small, a brute force solution using permutations is acceptable. The formula for the total distance for a given permutation P = (p₀, p₁, \(\dots\), p_n-1) is given by:

\[ D = \sum_{i=0}^{n-1} d(p_i, p_{(i+1) \mod n}) \]

inputFormat

The first line of input contains an integer n (2 ≤ n ≤ 10) 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 distance from city i to city j.

outputFormat

Output a single integer representing the minimum travel distance to start at a city, visit every 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