50060. Traveling Salesman

I'm a slow walker, but I never walk backwards.

Task Description

Given a set of cities and distance between each pair of cities, the problem is to find total distance of the shortest route that visits every city exactly once and returns to the origin city.

For example, consider the graph shown in figure below. A Traveling Salesman tour in the graph is $1-2-4-3-1$. The cost of the tour is $10+25+30+15$ which is $80$.

p10139.

Subtask

  • 95pt. $3\lt N \leq 13$.
  • 5pt. $N=14$. For this subtask you need to "cut" the search once you realize that any further selection from this variation will not be better than the best one you have seen. That is, if you know the current best solution is $6$. If your current selection already has a distance $8$, then it is meaningless to continue.

Input Format

There is only one test case. The first line has one integer N indicating the number of cities. Following $N$ lines with $N$ non-negative integers. The $j_{th}$ integer of the $i_{th}$ line will describe the distance from city $i$ to city $j$. It is guaranteed the input will always be a symmetric matrix and the $i_{th}$ integer of the $i_{th}$ line will always be $0$.

  • $3 \lt N \leq 14$
  • $0 \lt \textit{distance between any pair of cities} \lt 100$

Output Format

There is one line in the output. The line has an integer indicating the total distance of the shortest route.

Sample Input 1

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

Sample Output 1

80

Discussion