有一個推銷員要走訪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)。
0 — 4
/ / \
1 2 3
第一行是正整數n,代表城市的數量,城市是以0~n-1編號,接下來有n-1行是道路的資料,每行三個整數a,b與w,代表此道路連接城市a與b,道路的長度是w。n不超過50000,每條道路長度是不超過100的正整數。
第一行輸出最短的旅行距離,第二行輸出拜訪順序,相鄰的數字之間要以一個空白間格。
5 1 0 1 0 4 1 2 4 1 4 3 1
8 0 1 0 4 2 4 3 4 0
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |