Entrega de Manzanas


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Bessie tiene dos manzanas rojas crujientes para entregar a sus amigas en el rebaño. Por supuesto ella recorre los C (1 \leq C \leq 200,000) caminos de vacas los cuales están organizados como el grafo usual que conecta P (1 \leq P \leq 100,000) pastizales convenientemente numerados de 1 a P, ningún camino de vaca va directamente de vuelta a un pastizal, los caminos de vacas son bidireccionales, cada camino de vaca tiene una distancia asociada, y lo mejor de todo, siempre es posible ir de un pastizal a cualquier otro pastizal. Cada camino de vaca conecta dos pastizales distintos P1_i (1 \leq P1_i \leq P) y P2_i (1 \leq P2_i \leq P) con una distancia entre ellos de D_i. La suma de todas las distancias D_i no excede 2,000,000,000.

¿Cuál es la distancia mínima total que Bessie debe desplazarse para llevar ambas manzanas iniciando en el pastizal PB (1 \leq PB \leq P) y visitando los pastizales PA1  (1 \leq PA1 \leq P) y PA2 (1 \leq PA2 \leq P) en cualquier orden. Todos estos tres pastizales, por supuesto, son distintos.

Considere este mapa de pastizales numerados entre corchetes y caminos de vacas con distancias.

                3        2       2
           [1]-----[2]------[3]-----[4]
             \     / \              /
             7\   /4  \3           /2
               \ /     \          /
               [5]-----[6]------[7]
                    1       2

Si Bessie comienza en el pastizal [5] y entrega manzanas en los pastizales [1] y [4], su mejor camino es:

5 -> 6-> 7 -> 4* -> 3 -> 2 -> 1*

con una distancia total de 12.

Entrada

  • Línea 1: La línea 1 contiene cinco enteros separados por espacios: C, P, PB, PA1 y PA2.

  • Lineas 2..C+1: La línea i+1 describe el camino de vaca i+1 nombrando los dos pastizales que conecta y la distancia entre ellos: Pi_1, Pi_2, D_i

Salida

En una sola línea la menor distancia que Bessie tiene que recorrer para entregar ambas manzanas.

Ejemplo de Entrada

9 7 5 1 4
5 1 7
6 7 2
4 7 2
5 6 1
5 2 4
4 3 2
1 2 3
3 2 2
2 6 3

Ejemplo de Salida

12

Comments

There are no comments at the moment.