Traveling Salesman Problem Solver

You are given a set of delivery locations and a distance matrix representing the distances between each pair of locations. Your task is to compute the minimum total distance required for a round-trip route starting and ending at the first location while visiting every other location exactly once.

Formally, let \(d[i][j]\) be the distance from location \(i\) to location \(j\). You need to determine the minimum cost of a route that starts at location 0, visits all \(n\) locations, and then returns to location 0. This can be written in LaTeX as:

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

Note: \(n\) (the number of locations) satisfies \(2 \le n \le 15\).

inputFormat

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

• The first line contains a single integer \(n\) (\(2 \le n \le 15\)) representing the number of locations.
• The next \(n\) lines each contain \(n\) space-separated integers. The \(j\)-th integer in the \(i\)-th line represents the distance from location \(i\) to location \(j\).

outputFormat

The output is written to standard output (stdout) and should be a single integer representing the minimum total distance of the round-trip route.

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

80