d121:
Q_8_15 樹上一位不回家的推銷員
Content
有一個推銷員要走訪 $n$ 個城市。這些城市以 $n-1$ 條道路連接，每條道路連接兩個不同的城市並且雙向可以通行，而且已知每一個城市都可以到達，不會有到達不了的狀 況。輸入道路的資料，請你幫推銷員找出一個最短的路徑走訪所有的城市，推銷員可以從任何城市開始，也不必回到開始的城市，只要每個城市至少到一次就可以。 舉例來說，如右圖，有 $5$ 個城市以 $4$ 條道路連接，假設 每條道路的長度都是 $1$。最短的拜訪路徑是 $(1,0,4,2,4,3)$，長度為 $5$。
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
5
Sample Input
#2
3 1 2 5 0 2 3
Sample Output
#2
8
測資資訊：
記憶體限制：
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
公開 測資點#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:
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||