貨郎問題 (AP325 Q-6-25)

有一個賣貨郎要旅行 \(n\) 個城市做生意並且回到他的家，由於路途遙遠，他希望走的路程總和越短越好，希望你幫他規劃最短路線。這 \(n\) 個城市由 \(0 \sim n-1\) 編號，他的家在編號 \(m\) 的城市。對任意兩個城市 \(i\) 與 \(j\)，已知兩者之間的距離是 \(d[i][j]\)，而且繞經第三地的路程絕對不會更短。

輸入格式

第一行有兩個整數 \(n\) 與 \(m\)。接下來 \(n\) 行每行 \(n\) 個非負整數是矩陣 \(d[i][j]\) 的內容，順序由上而下、由左而右，\(i\) 從 \(0 \sim n-1\)，\(j\) 從 \(0 \sim n-1\)。

限制

• \(1 \le n \le 16\)，\(0 \le m \le n-1\)。
• \(d[i][j] = d[j][i]\)，\(d[i][i] = 0\)，且 \(0 \le d[i][j] \le 100\)。
• 繞經第三地的路程絕對不會更短：對任意 \(i, j, k\)，\(d[i][j] \le d[i][k] + d[k][j]\)。

輸出格式

輸出最短總路程。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入 1

4 0
0 1 1 2
1 0 1 2
1 1 0 1
2 2 1 0

範例輸出 1

5

範例輸入 2

4 2
0 2 1 1
2 0 1 1
1 1 0 2
1 1 2 0

範例輸出 2

4

範例說明

範例一：走的順序與距離 \(0 \to 1 \to 2 \to 3 \to 0\)，距離總和 \(1 + 1 + 1 + 2 = 5\)。

範例二：走的順序與距離 \(0 \to 2 \to 1 \to 3 \to 0\)，距離總和 \(1 + 1 + 1 + 1 = 4\)。

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 6 章 Q-6-25，第 216 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。