\(2^{nd}\) round, November \(9^{th}\), 2013

Chances are that you have probably already heard of the travelling salesman problem. If you have, then
you are aware that it is an \(NP-ha\)rd problem because it lacks an efficient solution. Well, this task is an
uncommon version of the famous problem! Its uncommonness derives from the fact that this version
is, actually, solvable.
The travelling salesman is on a mission to visit N cities, each exactly once. The cities are represented by
numbers 1, 2, ..., N. What we know is the direct flight duration between each pair of cities. The
salesman, being the efficient man that he is, wants to modify the city visiting sequence so that the total
flight duration is the minimum possible.
Alas, all is not so simple. In addition, the salesman has a peculiar condition regarding the sequence. For
each city labeled K must apply: either all cities with labels smaller than K have been visited before the
city labeled K or they will all be visited after the city labeled K. In other words, the situation when one
of such cities is visited before, and the other after is not allowed.
Assist the poor fellow in his ambitious mission and calculate the minimum total flight duration needed
in order to travel to all the cities, starting from whichever and ending in whichever city, visiting every
city exactly once, so that his peculiar request is fulfilled.

In test data worth \(1/3\) of total points, N will be at most 10.
In test data worth \(1/2\) of total points, N will be at most 20.

The first line of input contains the positive integer N (\(2 \le N \le 1500\)), the number of cities.
Each of the following N lines contains N positive integers from the interval [0, 1000]. The number in
B^{th} place in the A^{th} row represents the flight duration between cities A and B; that number is equal to
the A^{th} number in the B^{th} row. When \(A = B\), that number is 0. Otherwise, it is a positive value.

The first and only line of output must contain the required minimum total flight duration.

생성자가 기록되지 않았습니다.

출처 COCI 2013/2014 Contest 2