URI Online Judge | 1751

# Intrepid Climber

Por Cristhian Bonilha, Universidade Tecnológica Federal do Paraná Brazil

Timelimit: 2

Who would guess? You climbed the highest mountain of your city. You are so excited about it that you need to tell it to all your friends, and you decided to start with those that are trying to be exactly where you are at this precise moment.

The mountain has N landmarks, and one of them is the top of the mountain, where you are now. Each of your friends that is climbing the mountain is in some other landmark, and you want to visit all of them. There are tracks that connect pairs of landmarks in such a way that there exists exactly one route (that is, a sequence of consecutive tracks) that goes down from the top of the mountain to each other landmark. To visit two friends in two different landmarks, you may have to go down some tracks, climb others, and go down others again. Going down the mountain is “easy”, so you do not consume energy when you go down through the tracks. But each time you climb a track, you consume a certain amount of energy. After visiting all your friends, you can just sit and rest.

For example, consider the mountain in the picture below, which has N = 6 landmarks. If your friends are in landmarks 5 and 2, you can visit both if you follow the sequence of landmarks 1 ↓ 2 ↑ 1 ↓ 3 ↓ 5, where ab means that you go down a track from landmark a to landmark b, and ab means that you climb a track from landmark a to landmark b. Another possible sequence is 1 ↓ 3 ↓ 5 ↑ 3 ↑ 1 ↓ 2.

Given the tracks between the landmarks, the energy required to climb them, and the landmarks where your friends are, compute the minimum total amount of energy required to visit all your friends from the top of the mountain.