Traveling Salesman Problem

You are given an integer N representing the number of cities, as well as an N × N matrix of distances, where the entry at row i and column j represents the distance from city i to city j. Your task is to compute the minimum possible distance required to start at city 0, visit every other city exactly once, and return to city 0.

In mathematical terms, if we let \( d_{ij} \) denote the distance from city \( i \) to city \( j \), you must find the permutation \( \pi \) of \( \{1, 2, \ldots, N-1\} \) that minimizes the cost: \[ \text{cost}(\pi) = d_{0,\pi(1)} + \sum_{i=1}^{N-2} d_{\pi(i),\pi(i+1)} + d_{\pi(N-1),0}. \]

Note that since the problem is NP-hard, you can assume that \( N \) will be small enough (e.g. \( N \leq 10 \)) for a brute-force solution to finish in reasonable time.

inputFormat

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

N
row_1
row_2
... 
row_N

Here, the first line contains a single integer N (the number of cities). Each of the following N lines contains N space-separated integers representing one row of the distance matrix.

outputFormat

Output to stdout a single integer representing the minimum total distance of the tour that starts at city 0, visits every city exactly once, and returns to city 0.

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

80