d102. P-8-1. 樹上的推銷員

內容

有一個推銷員要走訪 n 個城市並在結束後回到出發的城市。

這些城市以 n-1 條道路連接，每條道路連接兩個不同的城市並且雙向可以通行，而且已知每一個城市都可以到達，不會有到達不了的狀況。

輸入道路的資料，請你找出一個長度最短的程式走訪順序，因為這樣的順序很多，你必須輸出字典順序最小的那一個。字典順序是用來比較兩個序列的先後順序，其方法是由前往後找到第一個不相同的位置，該元素比較小的序列就是順序比較小，如同在英文字典中單字的順序一般。例如

(0,2,3,1)<(0,3,1,2)，又(0,3,2,1)<(1,0,2,3)。

輸入說明

第一行是正整數 n，代表城市的數量，城市是以 0~n-1 編號，

接下來有 n-1 行是道路的資料，每行三個整數 a,b 與 w，代表此道路連接城市 a 與 b，道路的長度是 w。n 不超過 50000，每條道路長度是不超過 100 的正整數。

輸出說明

第一行輸出最短的旅行距離，第二行輸出拜訪順序，相鄰的數字之間要以一個

空白間格。

範例輸入 #1

範例輸出 #1

8
0 1 0 4 2 4 3 4 0

範例輸入 #2

3
1 2 5
0 2 3

範例輸出 #2

16
0 2 1 2 0

測資資訊：

記憶體限制： 64 MB
不公開測資點#0 (20%): 1.0s , <1M
不公開測資點#1 (20%): 1.0s , <1K
不公開測資點#2 (20%): 1.0s , <1K
不公開測資點#3 (20%): 1.0s , <1M
不公開測資點#4 (20%): 1.0s , <1M

提示：

標籤:

圖論樹

出處:

AP325 [管理者：

TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」