時間限制 1000 ms ・ 記憶體限制 256 MB
題目描述
有 n 個地點與一串必須依序完成的 k 個任務。兩位外送員都從地點 1 出發，每個任務指定其中一人前往該任務地點，另一人留在原處。從 u 移至 v 的成本是給定的 cost[u][v]。 完成全部任務後，兩人都要再前往地點 n。求任務分工與最後返抵終點的最小總成本。
輸入格式
第一行為 n、k，2 ≤ n ≤ 2000，1 ≤ k ≤ n。第二行給 k 個互不重複的任務地點 p_i，1 ≤ p_i ≤ n。接著 n 行各有 n 個整數，構成 cost；0 ≤ cost[i][j] ≤ 50，cost[i][i]=0，cost[i][j]=cost[j][i]。
輸出格式
輸出最小總成本。
範例測資
範例輸入 1
5 3 1 4 2 0 5 9 9 1 5 0 7 9 9 9 7 0 2 7 9 9 2 0 9 1 9 7 9 0
範例輸出 1
28
範例輸入 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
35
請先登入後再提交程式碼
討論與題解
載入討論區…