d909: 公路局長好煩惱!?
標籤 :
通過比率 : 91% (71 人 / 78 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2017-11-19 20:50

內容

Waku是一個窮困的未開發國家,當地總統Ruby希望建造公路把各個城鎮連接起來好讓貨物能更順利運輸好提振經濟。

但是因為預算有限,所以總統希望你能幫他規劃用最少的錢把Waku的每個城鎮都連接起來,每條公路的起點跟終點都一定是城鎮而且公路是雙向的。

注意不是任兩個城鎮都可以建造公路連接,因為中間可能有很難克服的地形障礙(像火山、大海之類)

輸入說明

第一行有兩個整數N,M             

N ≤ 10000 ,M ≤ N*(N-1)/2

N代表城鎮數量

M代表所有可能建造的公路數目

接下來有M行

每一行格式 A B C,代表建造從編號A的城鎮到編號B的城鎮的公路所需的成本C 

城鎮編號範圍從0到N-1

輸出說明

輸出一個整數D代表建造公路把各個城鎮連接起來所需的最小預算

範例輸入
5 10
0 2 20
2 4 31
4 1 38
1 3 23
3 0 6
0 4 22
3 2 8
1 2 4
3 4 1
1 0 8
範例輸出
19
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (5%): 1.0s , <1K
不公開 測資點#1 (15%): 1.0s , <1M
不公開 測資點#2 (20%): 1.0s , <1M
不公開 測資點#3 (10%): 1.0s , <1M
不公開 測資點#4 (50%): 1.0s , <10M
提示 :
標籤:
出處:
jsw7524 [編輯:
netsphere (JSW)
]


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