IOI '08 - Cairo, Egypt
You are visiting a park which has
Since you like walking better than riding ferries, you want to maximize the sum of the lengths of the bridges you cross, subject to the constraints below.
- You can start your visit at an island of your choice.
- You may not visit any island more than once.
- At any time you may move from your current island
to another island that you have not visited before. You can go from to either by:- Walking: Only possible if there is a bridge between the two islands. With this option the length of the bridge is added to the total distance you have walked, or
- Ferry: You can choose this option only if
is not reachable from using any combination of bridges and/or previously used ferries. (When checking whether it is reachable or not, you consider all paths, including paths passing through islands that you have already visited.)
Note that you do not have to visit all the islands, and it may be impossible to cross all the bridges.
Task
Write a program that, given the
Constraints
, The number of islands in the park. , The length of bridge .
Note that the original in-contest memory limit was 128 MB (if you want to constrain yourself further, try getting it under 60 MB).
Input Specification
Your program must read from the standard input the following data:
- Line
contains the integer , the number of islands in the park. Islands are numbered from to , inclusive. - Each of the next
lines describes a bridge. The of these lines describes the bridge constructed from island using two integers separated by a single space. The first integer represents the island at the other endpoint of the bridge, the second integer represents the length of the bridge. You may assume that for each bridge, its endpoints are always on two different islands.
Output Specification
Your program must write to the standard output a single line containing one integer, the maximum possible walking distance.
Note int64
in Pascal or long long
in C/C++
to score full points on this problem.
Note
Subtasks
- (
points) will not exceed . - (
points) No additional constraints.
Sample Input
7
3 8
7 2
4 2
1 4
1 9
3 4
2 3
Sample Output
24
The
One way that you can achieve maximum walking distance follows:
- Start on island
. - Walk the bridge of length
to reach island . - Walk the bridge of length
to reach island . - Walk the bridge of length
to reach island . - Take the ferry from island
to island . - Walk the bridge of length
to reach island .
By the end, you are on island
The only island that was not visited is island
- You are not able to visit it by walking, because there is no bridge
connecting island
(where you currently stand) and island . - You are not able to visit it using a ferry, because island
is reachable from island , where you currently stand. A way to reach it: use the bridge , then use a ferry you already used to get from island to island , then the bridge , and finally the bridge .
Comments