回分類題庫
h075: D.阿克圖洛斯.蒙斯克的煩惱
關鍵字: NPSC 2010 高中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 25 Times / 24 Users | Submit : 61 Times / 27 Users | Accepted rate : 89%
題目加入時間 : 2012-11-04 02:21

Content: 简体中文

自從人類開始開發許多殖民行星,並和許多外星生物結下了樑子,各行星間的通訊管道已經變得日趨重要。當某個行星被攻打時,即可藉由通訊系統馬上呼叫鄰近行星的軍隊進行救援。

即使人類早已進軍太空多年,克卜魯星區的行星間通訊依然依靠著老式的無線電,在星區附近發生的超新星爆炸時常讓克卜魯星區的通訊系統部份斷線。這情形讓人類自治聯盟的最高統領阿克圖洛斯.蒙斯克大帝非常地擔憂。如果在通訊系統剛好斷線時邊緣殖民地遭到外星族群攻擊將有可能讓他失去這些領土。

假設原本行星 A, B, C 之間互相是可以通訊的,現在行星 A 和 B 之間的無線電被超新星爆炸干擾而斷訊而 A - C 和 B - C 依然是可以通訊的,那我們說 A 和 B 還是可以透過 C 行星互相通訊。

每兩個行星之間可擁有最多一個通訊頻道。每個通訊頻道都有一個通訊強度,代表這個頻道可以抵抗多大的干擾。每次的超新星爆炸都可以算出一個干擾值,星區中的所有通訊頻道都會受到一樣大的干擾,如果干擾值超過了或是剛好等於通訊強度,這個頻道就會斷線。

阿克圖洛斯.蒙斯克授予你這項任務:給你克卜魯星區的通訊頻道概況,請你算出這個通訊網路能承受多大的超新星爆炸電磁干擾而不致於讓某些行星與主星克哈星失去聯絡。

Input:

輸入檔第一行為一個數字 T,代表總共有幾組測試資料。

每組測試資料以 1 <= N <= 100000 和 0 <= M <= 100000 開頭,N 代表克卜魯星區的行星數量,由 0 到 N-1 編號,M 代表通訊頻道的數量。接下來 M 行用三個數字 Ai, Bi 和 Si 描述每一個頻道,代表 Ai 行星和 Bi 行星之間有一條強度為 Si 的頻道。其中 Ai 和 Bi 都是整數而 Si 是浮點數。

Output:

對於每一筆資料,輸出一個浮點數代表最少需要多大的干擾才能讓某些行星與克哈星(行星編號0)失去聯絡。請將這個數字四捨五入到小數點以下第4位。

如果無法讓任何星球與克哈星失去聯絡,輸出 "No way."。又假如某些星球在沒有干擾的狀況下就已經沒有音訊則輸出 "The empire of Arcturus is ending."。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
3 3
0 1 1.0
1 2 2.0
2 0 3.0
4 3
0 1 1.0
0 2 1.0
0 3 1.0
4 2
0 1 1.0
0 2 1.0

Sample Output :

2.0000
1.0000
The empire of Arcturus is ending.

Hint :

Author :

NPSC 2010 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum