Traveling Salesman Problem: Delivery Route Optimization

You are given a complete weighted graph representing a set of cities and the distances between them. The goal is to find the minimum total distance required for a delivery truck to visit every city exactly once and return to the starting city. This is a classic Traveling Salesman Problem (TSP).

The problem can be formulated using dynamic programming with bitmasking. Let ( dp[i][mask] ) represent the minimum cost to reach city ( i ) after having visited the set of cities represented by the bitmask ( mask ). The recurrence relation is given by:

[ dp[j][mask \cup {j}] = \min_{i \in mask} (dp[i][mask] + distance(i, j)) ]

Finally, the answer will be:

[ \min_{i} (dp[i][\text{END}] + distance(i, start)) ]

Here, ( \text{END} = 2^n - 1 ) represents the state when all cities have been visited.

inputFormat

Input is given from standard input. The first line contains an integer ( n ) representing the number of cities. The following ( n ) lines each contain ( n ) space-separated integers, where the ( j^{th} ) integer in the ( i^{th} ) line indicates the distance from city ( i ) to city ( j ). It is guaranteed that the distance from a city to itself is 0.

outputFormat

Output a single integer to standard output, representing the minimum total distance required to visit all cities exactly once and return to the starting city.## sample

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

80