Traveling Salesman Problem

This problem is a classic instance of the Traveling Salesman Problem (TSP). You are given an n x n matrix where the element \(d_{ij}\) represents the distance from city \(i\) to city \(j\). The task is to compute the minimum length of a Hamiltonian cycle that starts at city 0, visits every city exactly once, and returns to city 0.

The objective can be mathematically stated as follows:

\[ \min_{\pi}\left( d_{\pi(0)\pi(1)} + d_{\pi(1)\pi(2)} + \cdots + d_{\pi(n-2)\pi(n-1)} + d_{\pi(n-1)\pi(0)} \right) \]

Use dynamic programming with bitmasking to solve the problem efficiently.

inputFormat

The input is read from standard input (stdin). The first line contains a single 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 represents the distance from city (i) to city (j).

outputFormat

Output a single integer to standard output (stdout): the minimum length of the Hamiltonian cycle.## sample

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

80