Dragones de IslaGrande
Enojado porque el lanzamiento de la tercera parte de su película favorita se pospuso hasta junio de 2020, Megazar y Gigazar pensaron en su propio guion para el final de la trilogía: En un mundo donde los vikingos de IslaGrande pueden volar con dragones, hay islas. Bytezar, el jefe de la tribu vikinga en la Isla , conoce rutas de vuelo directo de ida y vuelta entre las islas. Para cada entre y , la ruta une las islas y y tiene una longitud .
En cada isla , () hay dragones de la especie que pueden volar sin detenerse a una distancia máxima de . En otras palabras, los dragones en la isla podrán recorrer cualquier ruta , () para la cual , sin importar qué otras vías de vuelo hayan hecho previamente.
Bytezar quiere ir de la isla a la isla para salvar a Terazar, su dragón. Para llegar allí, inicialmente tomará un dragón de la especie (en la isla ). Entonces, si en algún momento Bytezar está en una isla, () con un dragón de la especie , puede:
1. Vuela de la isla a otra isla con el dragón que tiene, usando una ruta directa entre las islas i y x, por supuesto solo si .
2. Cambiar el dragón de la especie que tiene con un dragón de la especie en la isla.
Tarea
a) Determine la distancia máxima Dmaxi característica de un dragón a la que Bytezar puede llegar sin cambiar el dragón que tomó originalmente de la isla .
b) Determine la distancia mínima que debe recorrer Bytezar para llegar de la isla a la isla .
Especificación de la Entrada
El archivo de entrada estándar contiene en la primera línea un número natural P. Para todas las pruebas de entrada, el número P solo puede tener el valor o el valor . En la segunda línea hay dos números naturales N y M que representan el número de islas, y el número de rutas directas entre islas respectivamente. En la tercera línea hay N números naturales, el tercero de ellos representa la distancia máxima que un dragón puede volar desde la Isla. Las siguientes líneas se describen en las siguientes líneas. Hay tres números naturales A, B y D en cada una de estas líneas, lo que significa que hay una ruta bidireccional de longitud D entre las islas A y B.
Especificación de la Salida
En el archivo de salida estándar se mostrará un único número natural.
Si el valor de es , solo se resuelve el requisito .
En este caso, el número que se muestra representará la distancia máxima Dmaxi de un dragón a la que Bytezar puede llegar sin cambiar el dragón que tomó originalmente de la isla .
Si el valor de es , solo se resolverá el requisito .
En este caso, el número que se muestra representará la distancia mínima que Bytezar debe recorrer para llegar de la isla a la isla .
Restricciones y especificaciones
- , para cualquier .
- , , para cualquier .
- , para cualquier .
- Se garantiza que Bytezar puede llegar a la isla .
- Se garantiza que la respuesta a cualquier requisito es un número natural menor que .
- Para resolver el primer requisito correctamente, se otorga el % de la puntuación de la prueba.
- Para la solución correcta del segundo requisito, se otorga el % de la puntuación de la prueba.
Ejemplos #1 de Entrada
1
5 6
6 3 13 20 26
1 2 5
1 3 7
1 5 10
2 3 6
3 4 5
3 5 14
Ejemplos #1 de Salida
20
Explicación #1
, por lo que se resolverá el requisito ).
Hay islas y rutas entre ellas. Bytezar comienza desde la isla con un dragón que puede volar una distancia de hasta . Con este dragón solo puede llegar a las islas , , y , ya que para llegar a la isla tendría que recorrer una ruta. Longitud mayor que .
La distancia máxima que un dragón en las islas , , o puede volar es por lo tanto (el dragón en la isla ). Se puede ver que el dragón que puede volar una distancia de estaba en la isla y es inaccesible.
Ejemplos #2 de Entrada
2
5 6
6 3 13 20 26
1 2 5
1 3 7
1 5 10
2 3 6
3 4 5
3 5 14
Ejemplos #2 de Salida
28
Explicación #2
, por lo que se resolverá el requisito ).
Hay islas y rutas entre ellas. Para cubrir una distancia mínima de entre las islas y , Bytezar sigue los siguientes pasos:
Vuela de la isla a la isla una distancia de con el dragón de la especie . Vuela de la isla a la isla una distancia de con el dragón de la especie . Cambia el dragón de la especie con el dragón en la isla , que puede volar una distancia máxima de . Vuela de la isla a la isla una distancia de con el dragón de la especie . Vuela de la isla a la isla una distancia de con el dragón de la especie .
En total corre una distancia de .
Comments
Esta disponible el algoritmo del problema
La prueba correcta es la que esta en el sitio, la que se imprimio tiene un error en la primera entrada, cuando se envio no se actualizo..