e392: 規劃規劃找獎勵
Tags :
Accepted rate : 7人/23人 ( 30% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-09-16 16:55

Content

現在你坐在教室裡面的椅子上,而且很巧的你要去找獎品。

獎品大概是要這樣找:現在一共有 N 個房間,編號 1 號到 N 號房間,透過 N - 1 個走廊連接起來,可以保證不論你從哪裡開始走都可以走到其他任意一個房間,而每個走廊都可以雙向走動而且可能有不一樣的長度。

你現在可以選擇一個房間 S 作為起點,另外一個房間 T 作為終點,並用所有路徑中最短的那條路線走過去,我們稱這個過程中走的走廊長度總和為路徑長。

但是你有一點懶因為走廊有一點長,請算出路徑長前 5N 短的路徑長度。

 


# 測試資料範圍

1. 對於佔得分 15% 的測試資料,保證:
N = 2
0 <= 單一走廊長度 <= 1,000,000
2. 對於佔得分 30% 的測試資料,保證:
1 <= N <= 1000
0 <= 單一走廊長度 <= 1,000,000
3. 對於佔得分 30% 的測試資料,保證:
1 <= N <= 10000
0 <= 單一走廊長度 <= 1,000,000,000
4. 對於佔得分 25% 的測試資料,保證:
1 <= N <= 100,000
0 <= 單一走廊長度 <= 1,000,000,000

Input

輸入第一行有一個數字 N 代表房間的數量
接著有 N - 1 行,每一行有三個數字 Ai, Bi, Ci,代表房間 Ai 和 Bi 之間有一條長度為 Ci 的走廊。

Output

總共輸出一行,為減少輸出總量,前 5k 短路中每隔 5 個數字輸出一個就好,具體來說請依序輸出第 5k (k = 1, 2,......, N) 短路的長度,若第 5k 短路不存在請輸出 -1 。

Sample Input #1
5
1 2 4
2 3 5
1 4 6
3 5 8
Sample Output #1
9 23 -1 -1 -1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (7%): 2.5s , <1K
公開 測資點#1 (8%): 2.5s , <1K
公開 測資點#2 (7%): 2.5s , <1M
公開 測資點#3 (7%): 2.5s , <1M
公開 測資點#4 (8%): 2.5s , <1M
公開 測資點#5 (8%): 2.5s , <1M
公開 測資點#6 (7%): 2.5s , <1M
公開 測資點#7 (7%): 2.5s , <1M
公開 測資點#8 (8%): 2.5s , <1M
公開 測資點#9 (8%): 2.5s , <1M
公開 測資點#10 (6%): 2.5s , <10M
公開 測資點#11 (6%): 2.5s , <10M
公開 測資點#12 (6%): 2.5s , <10M
公開 測資點#13 (7%): 2.5s , <10M
Hint :
Tags:
出處:
[管理者:
boook (boook)
]


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