最後因為經費不足， kevin 將大城市建造成了 N 點 N - 1 邊的樹(保證任兩點連通)
kevin把 N 個城市分成了住宅城市和商業城市，現在選擇首都變成了問題
kevin 想要挑一個住宅城市當做首都，並希望他能從首都出發快速的經過完每個商業城市。
同樣的由於經費上的不足，kevin 需要一個妥善的評估。
所以現在，你來評估。
第一行有一個數字 N 代表 kevin 有 N 個城市
接下來有 N - 1 行 每一行有三個數字 u , v , d
代表 u 和 v 之間有一條距離為 d 的雙向道路
最後一行有 N 個數字
0 代表這個城市為住宅城市
1 代表這個城市為商業城市
對於每一個住宅城市，請輸出從這個城市出發最少要走多遠才能走完所有的商業城市
5 1 2 1 1 3 1 3 4 1 3 5 1 1 0 1 0 1
3 4
測試資料中
前30% N <= 2000
後70% N <= 500000
100% 0 < d <= 10 ^ 9
對於住宅城市2
2->1->3->5 最少3步能走完所有商業城市
對於住宅城市4
4->3->5->3->1 最少4步能走完所有商業城市
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||