c527: kevin 的新首都
標籤 :
通過比率 : 88% (7 人 / 8 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-02-12 18:15

內容

最後因為經費不足, 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
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (6%): 1.0s , <1M
公開 測資點#1 (6%): 1.0s , <1M
公開 測資點#2 (6%): 1.0s , <1M
公開 測資點#3 (6%): 1.0s , <1M
公開 測資點#4 (6%): 1.0s , <1M
公開 測資點#5 (14%): 2.0s , <50M
公開 測資點#6 (14%): 2.0s , <50M
公開 測資點#7 (14%): 2.0s , <50M
公開 測資點#8 (14%): 2.0s , <50M
公開 測資點#9 (14%): 2.0s , <50M
提示 :

測試資料中

前30% N <= 2000

後70% N <= 500000

100%  0 < d <= 10 ^ 9

 

對於住宅城市2

2->1->3->5 最少3步能走完所有商業城市

對於住宅城市4

4->3->5->3->1 最少4步能走完所有商業城市

標籤:
出處:
[編輯:
boook (boook)
]


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