Traveling Salesman Tour 2

The traveling salesman problem, TSP for short, is one of the most important problems in computer science. Several variants of it exist. This task uses the most common form.

Cities are numbered 1 through $N$, and roads run between cities. Some pairs of cities have no road. A salesman wants to plan a tour that starts at one city, passes through all $N$ cities, and returns to the city he started from. He may not go back to a city he has already visited. Returning to the starting city at the very end is the only exception. Many such tours exist, and he wants the plan with the smallest total cost.

The cost of moving between cities is given as a matrix $W$. $W[i][j]$ is the cost of going from city $i$ to city $j$. The costs are not symmetric, so $W[i][j]$ may differ from $W[j][i]$. Every travel cost is a positive integer, and $W[i][i]$ is always 0. There are cases where city $j$ cannot be reached from city $i$, and such a case is written as $W[i][j] = 0$.

Given $N$ and the cost matrix, write a program that finds the minimum cost of the salesman's tour.

The first line contains the number of cities $N$. ($2 \le N \le 10$) Each of the next $N$ lines contains $N$ entries of the cost matrix. Each entry is a positive integer no greater than 1,000,000, and 0 is given when the move is impossible. $W[i][j]$ is the cost of going from city $i$ to city $j$.

Every input allows at least one tour.

Print the minimum cost of the salesman's tour on the first line.