Traveling Salesman Problem (TSP) using Dynamic Programming

You are given a complete directed weighted graph with n cities. The cost of traveling from city i to city j is provided in a cost matrix. Your task is to compute the minimum cost required to start from city 1, visit every city exactly once, and return to city 1.

This problem can be formalized as follows:

Given a cost matrix \(C\) of size \(n \times n\), find a permutation \(\pi\) of \(\{1, 2, \dots, n\}\) such that:

[ \min_{\pi} \left{ C_{1,\pi(2)} + C_{\pi(2),\pi(3)} + \cdots + C_{\pi(n),1} \right} ]

Implement an algorithm based on dynamic programming with bit masking to solve this problem efficiently.

inputFormat

The first line of input contains an integer n representing the number of cities. Each of the next n lines contains n space-separated integers representing the cost matrix. The j-th integer in the i-th line denotes the cost of traveling from city i to city j.

For example:

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

outputFormat

Output a single integer representing the minimum cost to complete the trip starting at city 1, visiting every city exactly once, and returning to city 1.

## sample

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

80

</p>