d107: P_8_1 樹上的推銷員
Tags : ch8
Accepted rate : 2人/2人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-04-16 01:09

Content

有一個推銷員要走訪 $n$ 個城市並在結束後回到出發的城市。這些城市以 $n-1$ 條道路連接,每條道路連接兩個不同的城市並且雙向可以通行,而且已知每一個城市都可以到達,不會有到達不了的狀況。

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

舉例來說,如下圖,有5個城市以4條道路連接,假設每條道路的長度都是1。字典順序最小的最短拜訪順序是 $(0,1,0,4,2,4,3,4,0)$。

Input

第一行是正整數 $n$,代表城市的數量,城市是以 $0 \sim (n-1)$ 編號。

接下來有 $(n-1)$ 行是道路的資料,每行三個整數 $a , b$ 與 $w$ ,代表此道路連接城市 $a$ 與 $b$,道路的長度是 $w$。

$n$ 不超過 $50000$,每條道路長度是不超過 $100$ 的正整數。

Output

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

Sample Input #1
5
1 0 1
0 4 1
2 4 1
4 3 1
Sample Output #1
8
0 1 0 4 2 4 3 4 0
Sample Input #2
3
1 2 5
0 2 3
Sample Output #2
16
0 2 1 2 0
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
Hint :
Tags:
ch8
出處:
Prof. Wu [管理者:
ktlai (K.我已霸榜.Tlai)
]


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