|
Темы:
Hamilton cycle
Hamilton cycle
Simple puzzles
His Majesty King Bubei II wished to travel around his domain. At the same time, the route has the following wishes:
1) the route should take the least possible time (royal time – is a very valuable thing and should be protected);
2) the route must include all the settlements exactly once (if the king misses a settlement, then its inhabitants will be outraged by the royal inattention and stop paying taxes; if the king visits a settlement more than once, then the inhabitants of the remaining settlements items will also be indignant)
3) the route must begin and end in the capital of the state (having traveled around his possessions, the king must immediately get down to business). The capital is included in the route exactly 2 times: as a point of departure and as a destination, it cannot be an intermediate settlement of the route.
Write a program that uses the road map of the kingdom to find such a route or determines that it is impossible to fulfill all the requirements.
Input
first enter the number N (natural, does not exceed 10) – the number of settlements in the kingdom. Then follows N lines of N numbers in each – travel time between settlements (time – is a non-negative integer, does not exceed 500; if time = 0, then this means that there is no way between some settlements). Settlement No. 1 is the capital of the state.
Imprint
print the least total time that His Majesty will spend on a detour around his domains, or the number -1 if it is impossible to build a route with the given properties.
Examples
| # |
Input |
Output |
| 1 |
1
0 |
0 |
| 2 |
2
0 1
10 |
2 |
| 3 |
2
0 85
85 0 |
170 |
|