Traveling Salesman Problem (TSP)

You are given n cities and a distance matrix representing the distances between every pair of cities. Your task is to find the shortest possible route that visits each city exactly once and returns to the starting city.

The distance matrix is provided such that the value inf (or infinite) represents the absence of a direct route between two cities. If it is impossible to visit all cities due to disconnected paths, your program should output "No solution".

Note: The problem is NP-hard, so the input size will be small (n ≤ 10) ensuring that an exhaustive search using permutations is feasible.

inputFormat

The first line of input contains a single integer n (2 ≤ n ≤ 10), the number of cities.

The next n lines each contain n space-separated values. Each value is either a non-negative integer representing the distance between two cities or the string inf representing an infinite distance (i.e., no direct path is available).

outputFormat

Output a single line containing the length of the shortest route that visits every city exactly once and returns to the start. If no such route exists, output the string "No solution".

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

80