b117: TOI2008 4. 地道問題
Tags :
Accepted rate : 135人/164人 ( 82% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 01:30

Content
在一個神祕的城堡中,其地底建造了許多地道及房間。每間房間
連到其他房間的通道各有不同的柵門,且其柵門有特別的設計,有些
只能由內向外開,有些則只能由外向內開。國王把這些房間用來當作
囚房,除了一間房間做為侍衛休息室以外,其他每間房間皆做為一個
囚犯的囚房。這些囚犯每天白天負責工作,到了晚上每位囚犯有專屬
的侍衛,將他們一一帶到囚房。

由於要防止囚犯脫逃,除了侍衛休息室以外,地道及房間中皆沒
有燈光。因此每天每位侍衛必須分配一個油燈,從侍衛休息室將囚犯
帶到他們的房間,再回到侍衛休息室,在這段時間內皆必須點亮油
燈。國王是個很節儉的人,為了節省侍衛油燈所消耗的油,他派人根
據房間之間的地道長度所需行走時間,量測出經過每段通道使用油燈
的耗油量。國王精打細算的要求這些侍衛每天使用油燈的耗油總量必
須為最低。但由於侍衛將囚犯帶到房間的時間可能不同,因此不必考
慮侍衛共用油燈的可能。

請以一個程式,根據所給房間通道及經過房間通道所需的耗油
量,找出侍衛每天使用油燈的最低耗油總量。
Input

第一行輸入兩個正整數M 及N以空白區分,1<=M<=1000000,
1<=N<=1000000,其中M表示房間總數,N表示房間之間的通道總
數。

接下來的N行,每一行輸入三個正整數P、Q、及R,表示從房間P
可進入一個通道到房間Q,且經過該通道需要消耗R單位的油。所有
通道的耗油量總和將小於1000000000。

各房間分別以一個1到M的正整數表示,且侍衛休息室固定設在編
號1的房間。

Output
 輸出侍衛每天使用油燈的最低耗油總量。若所給通道資料無法由
侍衛休息室通到某一間房間,請輸出0。
Sample Input #1
2 2 
1 2 10 
2 1 25 
4 6 
1 2 10 
2 1 60 
1 3 20 
3 4 10 
2 4 5 
4 1 50 
Sample Output #1
35
210
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 10.0s , <1M
Hint :
Tags:
出處:
2008TOI研習營初選


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