Asymmetric Traveling Salesman Problem

In a certain region, there are \( n\ (2\le n\le 20) \) villages. A salesman from a store located in village 1 must travel to each of the other villages exactly once and then return to village 1. The distance between any two villages is given by \( s \) with \( 0<s<1000 \), and note that the distance from village A to village B can be different from that from B to A. Your task is to find the route with the minimum total travelling distance.

The problem can be formulated as a Traveling Salesman Problem (TSP) where you are given a directed weighted graph and must compute the minimum cost cycle that starts and ends at node 1 while visiting every other node exactly once.

inputFormat

The first line of input contains a single integer \( n \) representing the number of villages. This is followed by \( n \) lines, each containing \( n \) integers. The j-th integer in the i-th line denotes the distance from village i to village j. The distance from a village to itself will be 0.

outputFormat

Output a single integer that is the minimum travelling cost of a route that starts at village 1, visits every other village exactly once, and returns to village 1.

sample

2
0 10
20 0

30