P7751 [COCI 2013/2014 #2] PUTNIK

Salesman Sept has a task: to visit $N$ cities (numbered from $1$ to $N$), and each city must be visited **exactly once**. Among these $N$ cities, there is a flight between every pair of cities. Sept values efficiency, so he wants to minimize the total time spent flying. For this, he may change the visiting order of the cities. However, Sept has a strange requirement for the visiting order: - There is no requirement for city $1$. - If he is going to visit city $K(K\in[2,N])$, then all cities with numbers smaller than $K$ must be visited either all before visiting city $K$, or all after visiting city $K$.\ In other words, for two cities $X,Y(1\le X,Y< K)$, it is not allowed that city $X$ is visited before city $K$ while city $Y$ is visited after city $K$. Under these restrictions, given the time needed to take flights between every pair of cities, find the minimum total flying time Sept spends.

The first line contains an integer $N$, the number of cities. The next $N$ lines each contain $N$ integers. Let $(A,B)$ denote the $B$-th number in the $A$-th line. Then: - $(A,B)$ is the time needed to take a flight between cities $A$ and $B$. - If $A=B$, then $(A,B)=0$. - $(A,B)=(B,A)$.

Output one integer in a single line, the minimum total flying time Sept spends.

#### Explanation of Sample 1 The order $\tt2,1,3$ or $\tt3,1,2$ is valid. Note that $\tt1,3,2$ takes less time, but it does not satisfy Sept's strange requirement. #### Explanation of Sample 2 The order $\tt3,1,2,4$ or $\tt4,2,1,3$ is valid. #### Constraints **This problem does not use bundled testdata, and subtasks will not be shown in judging.** - Subtask 1 $\tt(40pts)$: $2\le N\le 10$. - Subtask 2 $\tt(20pts)$: $2\le N\le 20$. - Subtask 3 $\tt(60pts)$: no special restrictions. For $100\%$ of the data, $2\le N\le 1500$, $0\le (A,B)\le 10^3$. #### Source **This problem is translated from [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 2](https://hsin.hr/coci/archive/2013_2014/contest2_tasks.pdf) _T4 PUTNIK_.** According to the original testdata setup, the full score of this problem is $120$ points. Translated by ChatGPT 5