現在你坐在教室裡面的椅子上，而且很巧的你要去找獎品。
獎品大概是要這樣找：現在一共有 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
輸入第一行有一個數字 N 代表房間的數量
接著有 N - 1 行，每一行有三個數字 Ai, Bi, Ci，代表房間 Ai 和 Bi 之間有一條長度為 Ci 的走廊。
總共輸出一行，為減少輸出總量，前 5k 短路中每隔 5 個數字輸出一個就好，具體來說請依序輸出第 5k (k = 1, 2,......, N) 短路的長度，若第 5k 短路不存在請輸出 -1 。
5 1 2 4 2 3 5 1 4 6 3 5 8
9 23 -1 -1 -1
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||