Traveling Salesman Problem: Minimum Tour Weight

You are given a weighted, undirected graph with N nodes represented by an N x N adjacency matrix. The task is to find the shortest path (minimum total weight) that starts from node 0 and visits every node exactly once. This is the famous Traveling Salesman Problem (TSP). Note that if there is no valid path that visits every node exactly once (for example, if an edge does not exist, represented by a weight of -1), the program should output -1.

The solution often involves dynamic programming with bitmasking. The state space can be described as having 2^N possible subsets of visited nodes, and the complexity is typically O(N·2^N), which is feasible for smaller N.

Use the following latex formatted formulas where appropriate: the state space size is given by \(2^N\) and the recurrence relation is: \(dp[mask][i] = \min_{j \notin mask} \{ dp[mask \cup \{j\}][j] + cost(i, j) \}\).

inputFormat

The input is read from the standard input (stdin) and is formatted as follows:

• The first line contains a single integer N representing the number of nodes.
• The next N lines each contain N space-separated integers. The j-th integer on the i-th line represents the weight of the edge from node i to node j. A value of -1 indicates that there is no direct edge between those nodes.

outputFormat

Output a single integer to the standard output (stdout) which is the minimum total weight of a tour that starts at node 0 and visits every node exactly once. If no such tour exists, output -1.

## sample

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

80

</p>