Traveling Salesman Problem (TSP)

In this problem, you are given an integer (N) representing the number of castles and an (N \times N) matrix where the element in the (i^{th}) row and (j^{th}) column represents the length of the bridge between castle (i) and castle (j). The task is to determine the minimum length of the path that visits every castle exactly once and returns to the starting castle. This is a classic Traveling Salesman Problem (TSP) which can be solved using brute force for smaller values of (N). The input is read from standard input and the output is printed to standard output.

inputFormat

The first line of input contains an integer (N) (the number of castles). The following (N) lines each contain (N) space-separated integers representing the bridge lengths between castles. Specifically, the (j^{th}) number in the (i^{th}) row is the length from castle (i) to castle (j).

outputFormat

Output a single integer which is the minimum total length required to visit each castle exactly once and return to the starting castle.## sample

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

80