回『原創/不分類題庫』
c178: 快速旅行推銷員問題
標籤 :

通過比率 : 50% (2 人 / 4 人 ) (非即時)
評分方式: Tolerant , 記憶體限制: 64 MB
公開 測資點 1 (6%): 1.0s , <1K
公開 測資點 2 (6%): 1.0s , <1K
公開 測資點 3 (6%): 1.0s , <1K
公開 測資點 4 (6%): 1.0s , <1K
公開 測資點 5 (6%): 1.0s , <1K
公開 測資點 6 (6%): 1.0s , <1K
公開 測資點 7 (6%): 1.0s , <1K
公開 測資點 8 (6%): 1.0s , <1K
公開 測資點 9 (6%): 1.0s , <1K
公開 測資點 10 (6%): 1.0s , <1K
公開 測資點 11 (6%): 1.0s , <1K
公開 測資點 12 (6%): 1.0s , <1K
公開 測資點 13 (7%): 1.0s , <1M
公開 測資點 14 (7%): 1.0s , <1M
公開 測資點 15 (7%): 1.0s , <1M
公開 測資點 16 (7%): 1.0s , <1M
最近更新 : 2017-04-01 17:29

內容 :


給一組城市和每一個城市之間的距離,請找出從起點城市出發,經過所有城市且不重複回到起點城市的最短距離和。

例如,走訪順序為 $1-2-4-3-1$. 距離總和為 $10+25+30+15 = 80$.

輸入說明 :

只有一組測資,每組第一行有一個整數 $N$,表示有 $N$ 座城市,接下來會有 $N$ 行,每行上有 $N$ 個非負整數 $D_{i, j}$ 表示節點 $i$ 到節點 $j$ 的距離,如果 $D_{i, j} = 0$,視同沒有邊。

你可以假設每一條邊可能是單向的,保證至少一條 TSP 路徑。

輸出說明 :

輸出一行最小距離和。

範例輸入 : help
若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0
範例輸出:
80
提示 :
標籤:
出處:
批改娘 (管理:morris1028)

本題狀況 本題討論 排行