Background

The testdata for this problem is extremely large ($> 4$ GB). On Luogu, the last two test points of subtask 4 and the last test point of subtask 6 have been removed. The judge may need 2 to 4 minutes to load all test points.

Since reading the testdata takes a lot of time (and in the original contest it seems this was not counted in the program runtime), the time limit of this problem is doubled compared to the original time limit.

The testdata for this problem is generated locally using the official data generator provided by the contest. Due to cross-platform differences, it may differ from the original problem, but the generation commands used are exactly the same.

The removed test points can be judged at https://www.luogu.com.cn/problem/U661101.

Problem Description

A group of people arrived in a wilderness to develop it. After a lot of effort, they created $m$ farms, and they also built some roads connecting these farms. Each road connects two different farms. Because building roads is difficult, they built only $m-1$ roads in total, but between any two farms there is a path of positive length connecting them directly or indirectly. Mr. Wang owns $n$ of these farms, but these farms are not necessarily all directly connected. It may be the case that to travel between two of Mr. Wang’s farms, one must pass through other people’s farms.

Mr. Wang labels his farms from $1$ to $n$, where farm $1$ is also his home. He recorded the distances between every pair of his farms, and he wants to plan a shortest route that starts from his home (farm $1$), visits all of his farms, and finally returns to his home. Of course, for the planned route, the order and the number of times each farm is visited are not restricted, and the route may also pass through other people’s farms. Note that Mr. Wang has no information about other farms, therefore Mr. Wang can only compute the shortest route using the pairwise distances among these $n$ farms.

Please write a program to help Mr. Wang compute the length of the shortest route that can visit all of his farms and finally return to his home.

For example, suppose $m=5$, and Mr. Wang owns $n=4$ of them. The figure below shows the structure of all $m$ farms, where Mr. Wang’s farms are labeled with numbers $1 \sim 4$:

:::align{center} :::

Since Mr. Wang recorded the distances between every pair of his farms, we can represent these distances as the following distance matrix $d$, where $d_{i, j}$ (row $j$, column $i$) is the distance from farm $i$ to farm $j$. We can see that a distance matrix must be symmetric and has $0$ on the diagonal:

$$\begin{array}{|c|c|c|c|} \hline 0 & 4 & 8 & 10\\ \hline 4 & 0 & 6 & 8\\ \hline 8 & 6 & 0 & 2\\ \hline 10 & 8 & 2 & 0\\ \hline \end{array}$$

Using the information provided by the distance matrix, we can find that in this example, the shortest route is $1 \to 3 \to 4 \to 2 \to 1$, with total length $8+2+8+4=22$.

Input Format

$$\begin{aligned} &n \\ &d_{1,1} \; d_{1,2} \; d_{1,3} \; \cdots \; d_{1,n} \\ &d_{2,1} \; d_{2,2} \; d_{2,3} \; \cdots \; d_{2,n} \\ &d_{3,1} \; d_{3,2} \; d_{3,3} \; \cdots \; d_{3,n} \\ &\vdots \\ &d_{n,1} \; d_{n,2} \; d_{n,3} \; \cdots \; d_{n,n} \end{aligned}$$

• $n$ is the number of farms owned by Mr. Wang.
• $d_{i,j}$ is the distance from farm $i$ to farm $j$.
• The $m$ mentioned in the statement will not appear in the input.

Output Format

$$D$$

• $D$ is a positive integer, representing the length of the shortest route that starts from farm $1$, visits all of Mr. Wang’s farms, and finally returns to farm $1$.

3
0 2 4
2 0 2
4 2 0

8

4
0 4 8 10
4 0 6 8
8 6 0 2
10 8 2 0

22

Hint

Constraints

• $2 \leq n\leq 5000$.
• $0\leq d_{i,j}\leq 10^8$.
• If $i\neq j$, then $d_{i, j}> 0$.
• If $i = j$, then $d_{i, j} = 0$.
• For all $i, j$, $d_{i, j} = d_{j, i}$.
• It is guaranteed that there exists a positive integer $m\geq n$ such that there exists a connected graph with $m$ nodes and $m-1$ edges, where every edge has positive length, and $d_{i, j}$ is the distance matrix obtained by selecting $n$ nodes from it.
• All input numbers are integers.

Scoring

This problem has six subtasks, with constraints as listed below. Each subtask may contain one or more testdata. You will get the score for a subtask only if all testdata in that subtask are answered correctly.

Subtask	Score	Additional input constraints
1	7	$n=3$.
2	12	$n\leq 20$.
3	13	$n\leq 200$ and $m=n$, meaning all farms are owned by Mr. Wang.
4	21	$m=n$, meaning all farms are owned by Mr. Wang.
5	23	$n\leq 1000$.
6	24	No additional constraints.

Translated by ChatGPT 5