c178: 快速旅行推銷員問題
標籤 :
通過比率 : 50% (2 人 / 4 人 ) (非即時)
評分方式: Tolerant , 記憶體限制: 64 MB
最近更新 : 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 路徑。

  • $3 < N \leq 35$
  • $0 < \textit{distance between any pair of cities} \le 10000$
輸出說明

輸出一行最小距離和。

範例輸入
4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0
範例輸出
80
測資資訊:
公開 測資點#0 (6%): 1.0s , <1K
公開 測資點#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 (7%): 1.0s , <1M
公開 測資點#13 (7%): 1.0s , <1M
公開 測資點#14 (7%): 1.0s , <1M
公開 測資點#15 (7%): 1.0s , <1M
提示 :
標籤:
出處:
批改娘 [編輯: morris1028 (碼畜) ]
編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」