TopCoder

Thumb screenshot 2020 12 08 170353
自動姬
我要把自己丟進垃圾桶, 再把蓋子蓋起來

User's AC Ratio

91.7% (11/12)

Submission's AC Ratio

37.8% (45/119)

Description

小美冰淇淋將要遊覽一個有N個島嶼的公園。從每一個島i出發,只建造一座橋。橋的長度以Li表示。公園內總共有N座橋。儘管每座橋由一個島連到另一個島,但每座橋均可以雙向行走。同時,每一對這樣的島嶼,都有一艘專用的往來兩島之間的渡船。

相對於乘船而言,小美冰淇淋更喜歡步行(雖然他錢很多,但是他還是想要運動一下)。小美冰淇淋希望所經過的橋的總長度盡可能的長,但受到以下的限制。
  • 可以自行挑選一個島開始遊覽。
  • 任何一個島都不能遊覽一次以上。
  • 無論任何時間都可以由你現在所在的島S去另一個從未到過的島D。由S到D可以有以下方法:
    o 步行:僅當兩個島之間有一座橋時才有可能。對於這種情況,橋的長度會累加到步行的總距離;或者
    o 渡船:可以選擇這種方法,僅當沒有任何橋和/或以前使用過的渡船的組合可以由S走到D(當檢查是否可到達時,應考慮所有的路徑,包括經過曾遊覽過的那些島)。

注意,小美冰淇淋不必遊覽所有的島,也可能無法走完所有的橋。

身為小美冰淇淋的好碰友,你,需要編寫一個程序,給定N座橋以及它們的長度,按照上述的規則,計算小美冰淇淋可以走過的橋的最大長度。

•2 <= N <= 1,000,000,公園內的島嶼數目。
•1<= Li <= 100,000,000,橋i的長度。

Input Format

第一行包含N個整數,即公園內島嶼的數目。島嶼由1到N編號。

隨後的N行每一行用來表示一個島。第i 行由兩個以單空格分隔的整數,表示由島i築的橋。第一個整數表示橋另一端的島,第二個整數表示該橋的長度Li。你可以假設對於每座橋,其端點總是位於不同的島上。

Output Format

你的程序必須向標準輸出寫出包含一個整數的單一行,即可能的最大步行距離。

Sample Input

7
3 8
7 2
4 2
1 4
1 9
3 4
2 3

Sample Output

24

Hints

最後...冰淇淋融化了

Problem Source

HOJ

Subtasks

No. Testdata Range Score
1 0~20 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 1
6 1000 65536 262144 1
7 1000 65536 262144 1
8 1000 65536 262144 1
9 1000 65536 262144 1
10 1000 65536 262144 1
11 1000 65536 262144 1
12 1000 65536 262144 1
13 1000 65536 262144 1
14 1000 65536 262144 1
15 1000 65536 262144 1
16 1000 262144 262144 1
17 1000 262144 262144 1
18 1000 262144 262144 1
19 1000 262144 262144 1
20 1000 262144 262144 1