s225. 3. 貨物運送 - 高中生程式解題系統

內容

題目建置中，歡迎透過表單完善題目。

https://forms.gle/zYDuZnVvweiM3DTC6

---

城市中有 $n$ 個地點（編號 $1$ 到 $n$）以及 $k$ 個外送任務。所有任務必須嚴格按照順序 $p_1, p_2, \dots, p_k$ 完成。

現在有兩位外送員 A 與 B，初始位置都在地點 1。對於每一個任務 $p_i$，你必須指派 A 或 B 其中一人去完成。

當外送員從地點 $u$ 移動到地點 $v$ 時，產生的花費為 $cost[u][v]$。
當所有 $k$ 個任務都完成後，兩位外送員都必須回到地點 $n$。

請計算完成所有任務並讓兩人都回到終點的最小總花費。

輸入說明

第一行包含兩個整數 $n$ 和 $k$ ($2 \le n \le 2000, 1 \le k \le n$)。

第二行包含 $k$ 個整數 $p_1, p_2, \dots, p_k$ ($1 \le p_i \le n$)，代表任務序列，保證序列中的數字不重複。

接下來有 $n$ 行，每行包含 $n$ 個整數。第 $i$ 行的第 $j$ 個整數代表 $cost[i][j]$ ($0 \le cost[i][j] \le 50$)。

保證 $cost[i][i] = 0$ 且 $cost[i][j] = cost[j][i]$。

輸出說明

輸出一個整數，代表最小的總花費。

範例輸入 #1

範例輸出 #1

範例輸入 #2

8 6
8 6 3 4 1 7
0 7 7 1 8 6 9 8
7 0 2 7 1 6 4 5
7 2 0 3 4 3 8 5
1 7 3 0 5 4 3 4
8 1 4 5 0 2 4 2
6 6 3 4 2 0 9 3
9 4 8 3 4 9 0 7
8 5 5 4 2 3 7 0

範例輸出 #2

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (5%): 1.0s , <10M
公開測資點#1 (5%): 1.0s , <10M
公開測資點#2 (5%): 1.0s , <10M
公開測資點#3 (5%): 1.0s , <10M
公開測資點#4 (5%): 1.0s , <10M
公開測資點#5 (5%): 1.0s , <10M
公開測資點#6 (5%): 1.0s , <10M
公開測資點#7 (5%): 1.0s , <10M
公開測資點#8 (5%): 1.0s , <50M
公開測資點#9 (5%): 1.0s , <50M
公開測資點#10 (5%): 1.0s , <50M
公開測資點#11 (5%): 1.0s , <50M
公開測資點#12 (5%): 1.0s , <50M
公開測資點#13 (5%): 1.0s , <50M
公開測資點#14 (5%): 1.0s , <50M
公開測資點#15 (5%): 1.0s , <50M
公開測資點#16 (5%): 1.0s , <50M
公開測資點#17 (5%): 1.0s , <50M
公開測資點#18 (5%): 1.0s , <50M
公開測資點#19 (5%): 1.0s , <50M

提示：

標籤:

出處:

2026年3月 APCS 高級 [管理者： algo.seacow@gmail.com

algo.seacow@ ... (演算法海牛) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」