Animando las Vacas.
El Granjero Juan se ha vuelto tan perezoso que no quiere continuar manteniendo los senderos vacunos que actualmente le dan una manera de visitar cada uno de sus pastizales (convenientemente numerados
). Cada uno de los pastizales es el hogar de una vaca. GJ
planea quitar tantos de los
caminos como sea posible mientras se mantengan conectados los pastizales. Usted debe determinar con cuáles
senderos quedarse.
El sendero bidireccional conecta los pastizales
y
y requiere
tiempo para recorrerse. Ningún par de pastizales está conectado por más de un camino.
Las vacas están tristes de que su sistema de transporte esté siendo reducido. Usted debe visitar cada vaca al menos un día para animarla. Cada vez que usted visita el pastizal (aún si usted está de paso), usted debe hablarle a la vaca por tiempo
.
Usted pasara cada noche en el mismo pastizal (el cuál usted elegirá) hasta que las vacas se hayan recuperado de su tristeza. Usted terminará hablando con la vaca en el pastizal dormitorio al menos en la mañana cuando usted se levante y en la noche cuando usted haya vuelto a dormir.
Asumiendo que el Granjero Juan siga su sugerencia de cuales senderos dejar y usted elija el pastizal óptimo donde dormir, determine el tiempo mínimo que le tomará visitar cada vaca al menos una vez en un día.
Para sus primeros 10 envíos, a usted se le dará los resultados de correr su programa con una parte de los datos reales de prueba.
Entrada
- Línea 1: Dos enteros separados por un espacio:
y
- Líneas 2..N+1: La línea i+1 contiene un solo entero:
- Líneas N+2..N+P+1: La línea N+j+1 contiene tres enteros separados por espacios:
, y
.
Ejemplo de Entrada
5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
4 5 12Detalles de la Entrada
Salida
Un solo entero, el tiempo total que toma visitar todas las vacas (incluyendo las dos visitas a las vaca en su pastizal dormitorio).
Ejemplo de Salida
176Detalles de la Salida
Mantenga estos caminos:
Levántese en el pastizal y visite los pastizales en el orden
gastando un tiempo total de
antes de volver a dormir.
Comments
This comment is hidden due to too much negative feedback. Show it anyway.
Si