Entrega de Manzanas
Bessie tiene dos manzanas rojas crujientes para entregar a sus amigas en el rebaño. Por supuesto ella recorre los caminos de vacas los cuales están organizados como el grafo usual que conecta pastizales convenientemente numerados de a , 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 y con una distancia entre ellos de . La suma de todas las distancias 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 y visitando los pastizales y 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:
con una distancia total de 12.
Entrada
Línea 1: La línea 1 contiene cinco enteros separados por espacios: y .
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:
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