P15349 [TOIP 2025] 巡視農場

有一群人到了一個蠻荒之地開墾，經過很多努力，開闢了 $m$ 個農場，他們也開闢了一些道路連接這些農場，每一條道路連接兩個不同的農場。由於道路開闢困難，總共只開闢了 $m-1$ 條道路，但任何兩個農場之間，都有長度大於零的路徑直接或間接連接。王老先生擁有其中的 $n$ 個農場，不過這些農場不一定全部直接連接在一起，可能有兩個王老先生的農場之間，需要經過其他人的農場才能互相來回。 王老先生將他的農場由 $1$ 到 $n$ 編號，其中 $1$ 號農場也是他的住家。他記錄了他的任兩個農場之間的距離，想要規劃出一條從住家（$1$ 號農場）出發、巡視經過所有他的農場、最後回到住家的最短路徑。當然，對於規劃出的路徑，各個農場經過的順序與次數皆不限定，中間也可以經過其他人的農場。注意到王老先生並沒有其他農場的資訊，因此**王老先生只能透過這 $n$ 個農場兩兩之間的距離來計算最短路徑**。 請你撰寫一支程式，幫王老先生計算出最短的路徑長度，滿足該路徑能巡視經過所有他的農場，最後回到住家。 舉例來說，假設 $m=5$，而王老先生擁有其中的 $n=4$ 個農場。下圖表示了所有 $m$ 個農場的結構，其中王老先生的農場被標上了 $1\sim 4$ 的編號： :::align{center}  ::: 由於王老先生記錄了他的任兩個農場之間的距離，我們可以將這些距離表示成如下的距離矩陣 $d$，其中 $d_{i, j}$（第 $i$ 列的第 $j$ 行）是農場 $i$ 到 $j$ 的距離。可以發現，一個距離矩陣必然是對稱矩陣且對角線均為 $0$： $$ \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} $$ 而透過距離矩陣提供給我們的資訊，可以找出在這個例子中，最短的路徑是 $1 \to 3 \to 4 \to 2 \to 1$，長度為 $8+2+8+4=22$。

$$ \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$ 代表王老先生擁有的農場個數。 * $d_{i,j}$ 代表農場 $i$ 到 $j$ 的距離。 * 題敘中提到的 $m$ 並不會出現在輸入中。

$$D$$ * $D$ 為一正整數，代表王老先生從 $1$ 號農場出發、巡視經過所有他的農場、最後回到 $1$ 號農場的最短路徑長度。

### 測資限制 * $2 \leq n\leq 5000$。 * $0\leq d_{i,j}\leq 10^8$。 * 若 $i\neq j$，則 $d_{i, j}> 0$。 * 若 $i = j$，則 $d_{i, j} = 0$。 * 對於所有 $i, j$，$d_{i, j} = d_{j, i}$。 * 保證存在一個正整數 $m\geq n$，滿足存在一個 $m$ 點 $m-1$ 條邊、每條邊長度都大於零的連通圖，滿足 $d_{i, j}$ 為在其上取 $n$ 個點後的距離矩陣。 * 輸入的數字皆為整數。 ### 評分說明 本題共有六組子任務，條件限制如下所示。每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。 | 子任務 | 分數 | 額外輸入限制 | | :------: | :----: | ------------ | | 1 | 7 | $n=3$。 | | 2 | 12 | $n\leq 20$。 | | 3 | 13 | $n\leq 200$ 且 $m=n$，也就是所有的農場都是王老先生的。 | | 4 | 21 | $m=n$，也就是所有的農場都是王老先生的。 | | 5 | 23 | $n\leq 1000$。 | | 6 | 24 | 無額外限制。 |