d089: Q-6-25. 貨郎問題 (@@)
Tags : DP
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-09-23 21:33

Content

有一個賣貨郎要旅行 n 個城市做生意並且回到他的家,由於路途遙遠,他希望走的路

程總和越短越好,希望你幫他規劃最短路線。這 n 個城市由 0~n-1 編號,他的家在

編號 m 的城市。對任意兩個城市 i 與 j,已知兩者之間的距離是 d[i][j],而且繞

經第三地的路程絕對不會更短。

Input

第一行有兩個正整數n與m。接下來n行每行n個非負整數是矩陣d[i][j]

的內容,順序由上而下,由左而右,i 從 0~n-1,j 從 0~n-1。n < 17,,假設

d[i][j]=d[j][i], d[i][i]=0, 且 d[i][j] <= 100。

Output

最短總路程。

Sample Input
// 1
4 0
0 1 1 2
1 0 1 2
1 1 0 1
2 2 1 0
// 2
4 2
0 2 1 1
2 0 1 1
1 1 0 2
1 1 2 0
Sample Output
// 1
5
// 2
4
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1K
Hint :
Tags:
DP
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」