Traveling Salesman Problem - Minimum Tour Distance

This problem is a classic variation of the Traveling Salesman Problem (TSP). You are given an n × n matrix where the element \(a_{ij}\) represents the distance from city \(i\) to city \(j\). Your task is to compute the minimum total distance required to start at a city, visit all cities exactly once, and return to the starting city.

The mathematical formulation is as follows: Given a set of cities \(\{0, 1, \dots, n-1\}\) and a distance matrix \(D = (d_{ij})\), find a permutation \(\pi\) of \(\{0, 1, \dots, n-1\}\) that minimizes

[ TSP = d_{\pi(0)\pi(1)} + d_{\pi(1)\pi(2)} + \cdots + d_{\pi(n-2)\pi(n-1)} + d_{\pi(n-1)\pi(0)}. ]

Note that the input size is small (typically \(n \leq 10\)), so a brute-force approach using permutations is acceptable.

inputFormat

The first line contains an integer \(n\) representing the number of cities. The next \(n\) lines each contain \(n\) space-separated integers where the \(j^{th}\) number in the \(i^{th}\) line is the distance from city \(i\) to city \(j\).

outputFormat

Output a single integer representing the minimum tour distance required to 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