Minimal Travel Distance

You are given an integer \(n\) representing the number of cities and an \(n \times n\) matrix of integers where the element at the \(i\)-th row and \(j\)-th column represents the distance from city \(i\) to city \(j\). Your task is to find the minimal travel distance required to visit every city exactly once and return to the starting city.

Note: The distance matrix is symmetric and the diagonal elements are zero. Since the problem is NP-hard, the value of \(n\) will be small enough (typically \(n \leq 10\)) to allow a brute force approach using permutations.

The problem can be formulated as follows in LaTeX: \[ \text{Minimize } \sum_{i=1}^{n} d_{\pi(i)\pi(i+1)} \quad \text{with } \pi(n+1)=\pi(1) \] where \(\pi\) is a permutation of \(\{1,2,\dots,n\}\) representing the order in which the cities are visited.

inputFormat

The input is read from stdin and has the following format:

n
a11 a12 ... a1n
a21 a22 ... a2n
...
a n1 a n2 ... a nn

Where:

• \(n\) is the number of cities.
• \(a_{ij}\) represents the distance from city \(i\) to city \(j\).

outputFormat

Output a single integer representing the minimal travel distance required to visit all cities exactly once and return to the starting city. The result should be written to stdout.

4
0 20 42 35
20 0 30 34
42 30 0 12
35 34 12 0

97