uCoder | 1149 | Nível: 4 | Tempo Limite: 3
Alpinista Intrépido
Adaptado por erich.rodriguesf
Competição: SBC - ACM/ICPC - Maratona de Programação de 2014 - Final Nacional
Quem iria adivinhar? Você escalou a montanha mais alta de sua cidade. Você está tão animado sobre isso que você precisa dizer a todos os seus amigos, e você decidiu começar com aqueles que estão a tentar estar exatamente onde você está neste exato momento.
A montanha tem N marcos, e um deles é o topo da montanha, onde você está agora. Cada um de seus amigos que está escalando a montanha está em algum outro local de referência, e você pretende visitar todos eles. Existem trilhas que ligam os pares de pontos de referência, de tal forma que existe exatamente um percurso (isto é, uma sequência de trilhas consecutivas) que vai para baixo a partir do topo da montanha para cada outro ponto de referêmcia. Para visitar dois amigos em duas referências diferentes, você pode ter que descer em algumas trilhas, subir em outras, e descer outras novamente. Descer a montanha é "fácil", já que não consome muito sua energia quando você desce por uma trilha. Mas cada vez que você subir uma trilha, você consome uma certa quantidade de energia. Depois de visitar todos os seus amigos, você pode apenas sentar e descansar.
Por exemplo, considere a montanha na imagem abaixo, que tem N = 6 pontos de referência. Se seus amigos estão em referenciais 5 e 2, você pode visitar tanto se você seguir a seqüência de referências 1 ↓ 2 ↑ 1 ↓ 3 ↓ 5, onde a ↓ b significa que você desce uma trilha de uma referência a até uma referência b, e a ↑ b significa que você subir uma trilha de uma referência a até uma referência b. Outra sequência possível é 1 ↓ 3 ↓ 5 ↑ 3 ↑ 1 ↓ 2.
Dadas as trilhas entre os pontos de referência, a energia necessária para escalá-los, e os pontos de referência onde seus amigos estão, calcular o montante total mínimo de energia necessária para visitar todos os seus amigos a partir do topo da montanha.
Entrada
A primeira linha contém dois inteiros N e F (1 ≤ F < N ≤ 10⁵), representando, respectivamente, o número de pontos de referência e o número de seus amigos que estão subindo a montanha. Referenciais são identificados com números inteiros distintos entre 1 e N, sendo 1 o topo da montanha, onde você está inicialmente.
Cada uma das próximas N - 1 linhas descreve uma diferente trilha com três números inteiros A, B e C, o que indica que existe uma trilha de A a B, que vai para baixo e requer uma quantidade de energia C para ser escalado (1 ≤ A ≤ N , 2 ≤ B ≤ N, A = B e 1 ≤ C ≤ 100).
A próxima linha contém F diferentes inteiros L1, L2, …, LF (2 ≤ Li ≤ N para i = 1, 2, …, F), representando os marcos onde seus amigos estão. Você pode assumir que as trilhas entre os marcos são tais que existe exatamente uma rota que vai para baixo a partir do topo da montanha para cada outro referencial.
Saída
Apresente uma linha com um inteiro que representa o montante total mínimo de energia necessária para visitar todos os seus amigos a partir do topo da montanha.
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
4 2 |
0 |
|
4 2 |
2
|
|
6 2 |
2 |