P1171 The Traveling Salesman Problem

**The testdata has been updated.**

In a certain township, there are $n$ villages. A salesman needs to visit each village to sell goods. The distances $s_{i,j}$ between villages are known, and, in general, the road from village A to village B may be different from the road from village B to village A. To improve efficiency, he starts from the store, visits each village exactly once, and then returns to the village where the store is located. Assume the store is in village $1$. He does not know which route will minimize the total distance traveled. Please help him choose a route with the shortest total length.

The first line contains an integer $n$, the number of villages. The next $n$ lines each contain $n$ integers. In the $i$-th line, the $j$-th integer represents the distance $s_{i,j}$ of the one-way path from $i$ to $j$.

Output a single integer on one line, representing the length of the shortest route.

For all testdata, it is guaranteed that $2 \leq n \leq 20$, $1 \leq s_{i,j} < 10^3$. Translated by ChatGPT 5