TopCoder

西瓜
いつか、私を助けてね

User's AC Ratio

92.0% (138/150)

Submission's AC Ratio

37.1% (384/1035)

Tags

Description

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

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

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

Input Format

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

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

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

Output Format

輸出侍衛每天使用油燈的最低耗油總量。若所給通道資料無法由侍衛休息室通到某一間房間,請輸出0。

Sample Input 1

2 2
1 2 10
2 1 25

Sample Output 1

35

Sample Input 2

4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

Sample Output 2

210

Hints

Problem Source

原TIOJ1509 / TOI2008初選(prob 4)

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5