Traveling Salesman Problem (TSP) using Bitmask DP

You are given a set of n cities and a cost matrix \(C\) of size \(n \times n\) where \(C[i][j]\) represents the cost to travel from city \(i+1\) to city \(j+1\). Your task is to find the minimum cost route that starts from city 1, visits every city exactly once, and returns to city 1.

The problem can be formulated using the following recursive relation with bitmask dynamic programming:

[ \text{dp}(i, S) = \min_{j \notin S} { C[i][j] + \text{dp}(j, S \cup {j}) } ]

with the base case:

[ \text{dp}(i, {all}) = C[i][1] ]

Here, the set \(S\) is represented by a bitmask, and dp(0, 1) is our answer (using 0-indexing for cities, with city 1 represented by index 0).

inputFormat

The first line contains an integer n (the number of cities).
Each of the next n lines contains n space-separated integers representing the cost matrix.

Input Format Example:

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

outputFormat

Output a single integer which is the minimum cost of the tour that starts at city 1, visits every city exactly once, and returns to city 1.

Output Format Example:

80

## sample

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

80

</p>