內容
星際採礦公司「UniverseCraft」擁有 N（2≤N≤100000）個採礦星，這些採礦星分佈在宇宙的各個角落，因此星際採礦公司將它們用 N−1 條雙向星際航道連接。對於每一條航道，航道 j 將採礦星 Aj 和 Bj（1≤Aj, Bj≤N）連通，並通過此航道的所需時間為 Tj（1≤Tj≤1000），且由於星際採礦公司不希望浪費任何一顆採礦星，對於任意採礦星 Uj，其皆恰有一種通往採礦星 Vj 的航道組合（1≤Uj, Vj≤N），我們可以稱這個組合為採礦星 Uj 前往採礦星 Vj 的航線。
星際採礦公司規劃了 M（1≤M≤100000）條重要的貿易航線，第 i 條航線需要從採礦星 Ui 前往採礦星 Vi（1≤Ui, Vi≤N），而其航行時間即為兩採礦星路徑間所有航道時間的總和。為了提升整體運輸效率，星際採礦公司準備將其中一條航道升級為超級航道Ω，據計算，升級過後的航道通過所需的時間小於 1 阿秒，也就是說，升級後，該航道的通過時間可視為 0。
請你寫一個程式，協助星際採礦公司選擇一條航道，使得升級後 M 條貿易航線中，花費時間最長的那條航線的時間盡可能小。請輸出這個最小化後的最高航線時間。
輸入說明
第一行包含兩個正整數 N 與 M，分別代表採礦星數量與貿易航線數量。
接下來的 N−1 行，每行包含三個正整數 Aj, Bj, Tj，代表一條連接採礦星 Aj 與 Bj 的雙向航道，其通過時間為 Tj。
接下來的 M 行，每行包含兩個正整數 Ui, Vi，代表一條從星球 Ui 到 Vi 的貿易航線。
輸出說明
請輸出一個整數，代表優化後最大航線時間的最小可能值。
範例輸入
#1
6 3 1 2 2 2 3 3 2 4 4 3 5 5 3 6 1 1 5 4 6 2 3
範例輸出
#1
7
測資資訊：
記憶體限制：
64
MB
不公開 測資點#0 (5%): 0.5s , <10M
不公開 測資點#1 (5%): 0.5s , <10M
不公開 測資點#2 (5%): 0.5s , <10M
不公開 測資點#3 (5%): 0.5s , <1K
不公開 測資點#4 (5%): 0.5s , <10M
不公開 測資點#5 (5%): 0.5s , <10M
不公開 測資點#6 (5%): 0.5s , <10M
不公開 測資點#7 (5%): 0.5s , <10M
不公開 測資點#8 (5%): 0.5s , <10M
不公開 測資點#9 (5%): 0.5s , <10M
不公開 測資點#10 (5%): 0.5s , <10M
不公開 測資點#11 (5%): 0.5s , <1K
不公開 測資點#12 (5%): 0.5s , <10M
不公開 測資點#13 (5%): 0.5s , <10M
不公開 測資點#14 (5%): 0.5s , <10M
不公開 測資點#15 (5%): 0.5s , <1M
不公開 測資點#16 (5%): 0.5s , <1M
不公開 測資點#17 (5%): 0.5s , <1M
不公開 測資點#18 (5%): 0.5s , <1M
不公開 測資點#19 (5%): 0.5s , <1K
不公開 測資點#0 (5%): 0.5s , <10M
不公開 測資點#1 (5%): 0.5s , <10M
不公開 測資點#2 (5%): 0.5s , <10M
不公開 測資點#3 (5%): 0.5s , <1K
不公開 測資點#4 (5%): 0.5s , <10M
不公開 測資點#5 (5%): 0.5s , <10M
不公開 測資點#6 (5%): 0.5s , <10M
不公開 測資點#7 (5%): 0.5s , <10M
不公開 測資點#8 (5%): 0.5s , <10M
不公開 測資點#9 (5%): 0.5s , <10M
不公開 測資點#10 (5%): 0.5s , <10M
不公開 測資點#11 (5%): 0.5s , <1K
不公開 測資點#12 (5%): 0.5s , <10M
不公開 測資點#13 (5%): 0.5s , <10M
不公開 測資點#14 (5%): 0.5s , <10M
不公開 測資點#15 (5%): 0.5s , <1M
不公開 測資點#16 (5%): 0.5s , <1M
不公開 測資點#17 (5%): 0.5s , <1M
不公開 測資點#18 (5%): 0.5s , <1M
不公開 測資點#19 (5%): 0.5s , <1K
提示 ：
標籤:
出處:
[管理者：
lsstmoonis@g
...
(CERE)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||