Islands and Bridges

Lalit is in an amusement park. There are N islands in this park. These islands are connected with each other by bridges. For each pair of islands (a; b) there is exactly one way to go from a to b or vice versa. The bridges are of varying lengths. Lalit wants to traverse the paths between all possible pairs of vertexes. For example, if there are 4 vertexes numbered 1 to 4, he wants to go from 1 to 2, then from 1 to 3, then from 1 to 4, then from 2 to 3, then from 2 to 4, and finally from 3 to 4. Each time he starts a traversal, he buys an energy drink which gives him K units of energy. He must buy that drink for which K is at least equal to the length of the minimum bridge in the path he is going to traverse. The energy drink costs 1 unit of money per 1 unit of energy. So a drink with K units of energy will cost K units of money. Can you tell Lalit the minimum cost he will have to bear for completing this adventure.

**Input**

The rst line of input will contain an integer N, i.e., the number of islands.

The next N-1 lines will contain 3 space-separated integers x, y and l denoting that island x and island y are connected by bridge a bridge of length l.

**Output**

Output the minimum cost that Lalit will have to bear in order to complete his adventure.

**Test Data**

In all the subtasks, the integers x and y are in the range [1;N]. Integer l is in the range [1; 10^6].

Subtask 1 (20 Points): 1 < N < 300.

Subtask 2 (80 Points): 1 < N < 10^6.

**Sample Input**

41 2 22 3 12 4 3

**Sample Output**

10

Best solution I can think of is N^2, hints appreciated.

Read more…(313 words)

About the author:

Hemang Rajvanshy

Loading…

Join the discussion. Add a reply…

Post

About the author

Hemang Rajvanshy

Ready to join our community?

Sign up below to automatically get notified of new lists, get **reminders** to finish ones you subscribe to, and **bookmark** articles to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.