Traveling Salesman Problem - Shortest Route

You are given a set of ( n ) towns and a matrix ( D ) where ( D_{ij} ) represents the distance between town ( i ) and town ( j ). The task is to compute the shortest possible route starting from a specified town ( s ), visiting every other town exactly once, and returning to ( s ). This is a classic Traveling Salesman Problem (TSP) that can be solved using brute-force permutations since ( 2 \leq n \leq 10 ). The answer must be rounded to two decimal places.

The route cost for a permutation ( P = (p_1, p_2, \dots, p_{n-1}) ) is computed as: [ \text{Cost}(P) = D_{s,p_1} + \sum_{i=1}^{n-2} D_{p_i, p_{i+1}} + D_{p_{n-1}, s} ] Your task is to write a program that reads the input from standard input (stdin) and outputs the minimal route cost to standard output (stdout) in the required format.

inputFormat

The first line of input contains two integers: \( n \) (the number of towns) and \( s \) (the index of the starting town). \( n \) and \( s \) satisfy \( 2 \leq n \leq 10 \) and \( 0 \leq s < n \).

The next \( n \) lines each contain \( n \) space-separated integers. The \( j^{th} \) number in the \( i^{th} \) line represents the distance between town \( i \) and town \( j \), where \( 0 \leq D_{ij} \leq 10^5 \). It is guaranteed that \( D_{ii} = 0 \) for all \( i \).

outputFormat

Output a single floating-point number representing the minimum possible route cost. The result should be rounded to two decimal places. Print the answer to standard output (stdout).

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

80.00