c503: 旅行者_九國遊歷記<8> 小白去兔國
Tags : 旅行者
Accepted rate : 20人/23人 ( 87% ) [非即時]
評分方式:
Strictly

最近更新 : 2018-12-23 20:45

Content

小白則是到了兔國,兔國是鳥籠島上影視產業最發達的地方,島上60%的電影都是由此處產出,歌手及綜藝節目主持人也大部分是由兔國培養的,小白一來就連續聽了好即位歌手的演唱會,以及看了多部電影,某日,他想到街道上看看有沒有明星會剛好到街頭,於是就看到一群人聚集在樹下,便也湊了過去。

 

“難道真的有明星?”小白心想。

 

近點看才發現是一則公告,上面寫著數日後要在兔國各地舉辦演唱會聯播,總共有N個地點要聯播,每個地點只要和主機有連起來就會有訊號,需要架設線路,架設線路需要成本,每兩個地點之間架設成本都不同,由於地點數實在太多,廠商貼此公告聘人幫忙計算,只要能夠算出之人,在演唱會時候可以進後台和歌手見面。

 

“哇~那麼難得的機會怎麼可以錯過”小白興奮地說。

 

他隨即索取資料,返回住宿地方開始研究。

Input

第一行有整數N,代表有N個地點,接下來(N-1)*N/2行有三個整數s,t,w,代表s,t的成本為w

對於40%的測資,所有的w皆相同。

(0<N<=1000,1<=s,t<=N,0<=w<=1000)

Output

輸出最小成本。

Sample Input
3
1 2 3
1 3 5
2 3 2
Sample Output
5
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (40%): 1.0s , <1K
不公開 測資點#1 (60%): 1.0s , <10M
Hint :

主機在任一地點皆不會影響成本

Tags:
旅行者
出處:
107學年度板橋高中校內資訊學科能力競賽 [管理者:
snail (蝸牛)
]


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