Traveling Salesman Problem

In this problem, you are given an integer (n) representing the number of cities and a cost matrix (C) of size (n \times n) where (C[i][j]) is the cost to travel from city (i) to city (j). The task is to determine the minimum travel cost required to start from city 0, visit every other city exactly once, and return to city 0.

The problem can be formally stated as finding a permutation (\pi) of ({1, 2, \dots, n-1}) that minimizes the total cost:
[ \min_{\pi} \Bigl{ C[0][\pi(1)] + \sum_{i=1}^{n-2} C[\pi(i)][\pi(i+1)] + C[\pi(n-1)][0] \Bigr} ]
Note that the input size will be small enough to allow a brute-force (O((n-1)!)) approach.

inputFormat

The first line of input contains a single integer (n) representing the number of cities. The next (n) lines each contain (n) space-separated integers representing the cost matrix. The (j)-th integer in the (i)-th line indicates the cost (C[i][j]) to travel from city (i) to city (j).

outputFormat

Output a single integer representing the minimum possible travel cost to start at city 0, visit all cities exactly once, and return to city 0.## sample

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

80