Dragones de IslaGrande


Submit solution


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

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

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 N islas. Bytezar, el jefe de la tribu vikinga en la Isla 1, conoce rutas de vuelo directo de ida y vuelta entre las islas. Para cada j entre 1 y M, la ruta j une las islas A_j y B_j y tiene una longitud D_j.

En cada isla i, (1 \le i \le N) hay dragones de la especie que pueden volar sin detenerse a una distancia máxima de Dmaxi. En otras palabras, los dragones en la isla podrán recorrer cualquier ruta j, (1 \le j \le M) para la cual Dj \le Dmaxi, sin importar qué otras vías de vuelo hayan hecho previamente.

Bytezar quiere ir de la isla 1 a la isla N para salvar a Terazar, su dragón. Para llegar allí, inicialmente tomará un dragón de la especie 1 (en la isla 1). Entonces, si en algún momento Bytezar está en una isla, (1 \le i \le N) con un dragón de la especie T, puede:

1. Vuela de la isla i a otra isla x con el dragón que tiene, usando una ruta directa j entre las islas i y x, por supuesto solo si Dj \le Dmaxt.

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 1.

b) Determine la distancia mínima que debe recorrer Bytezar para llegar de la isla 1 a la isla N.

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 1 o el valor 2. 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 Dmaxi 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 P es 1, solo se resuelve el requisito a.

En este caso, el número que se muestra representará la distancia máxima Dmaxi de un dragón i a la que Bytezar puede llegar sin cambiar el dragón que tomó originalmente de la isla 1.

Si el valor de P es 2, solo se resolverá el requisito b.

En este caso, el número que se muestra representará la distancia mínima que Bytezar debe recorrer para llegar de la isla 1 a la isla N.

Restricciones y especificaciones

  • 1 \le N \le 800
  • 1 \le M \le 6000
  • 1 \le Dmax \le 50 000, para cualquier 1 \le y \le N.
  • 1 \le Aj, Bj \le N, para cualquier 1 \le j \le M.
  • 1 \le Dj \le 50 000, para cualquier 1 \le j \le M.
  • Se garantiza que Bytezar puede llegar a la isla N.
  • Se garantiza que la respuesta a cualquier requisito es un número natural menor que 10^9.
  • Para resolver el primer requisito correctamente, se otorga el 20 % de la puntuación de la prueba.
  • Para la solución correcta del segundo requisito, se otorga el 80 % 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

P = 1, por lo que se resolverá el requisito a).

Hay N = 5 islas y M = 6 rutas entre ellas. Bytezar comienza desde la isla 1 con un dragón que puede volar una distancia de hasta 6. Con este dragón solo puede llegar a las islas 1, 2, 3 y 4, ya que para llegar a la isla 5 tendría que recorrer una ruta. Longitud mayor que 6.

La distancia máxima que un dragón en las islas 1, 2, 3 o 4 puede volar es por lo tanto 20 (el dragón en la isla 4). Se puede ver que el dragón que puede volar una distancia de 26 estaba en la isla 5 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

P = 2, por lo que se resolverá el requisito b).

Hay N = 5 islas y M = 6 rutas entre ellas. Para cubrir una distancia mínima de 28 entre las islas 1 y N, Bytezar sigue los siguientes pasos:

Vuela de la isla 1 a la isla 2 una distancia de 5 con el dragón de la especie 1. Vuela de la isla 2 a la isla 3 una distancia de 6 con el dragón de la especie 1. Cambia el dragón de la especie 1 con el dragón en la isla 3, que puede volar una distancia máxima de 13. Vuela de la isla 3 a la isla 1 una distancia de 7 con el dragón de la especie 3. Vuela de la isla 1 a la isla 5 una distancia de 10 con el dragón de la especie 3.

En total corre una distancia de 5 + 6 + 7 + 10 = 28.


Comments


  • 5
    leocar  commented on Feb. 19, 2020, 11:10 p.m.

    Esta disponible el algoritmo del problema


  • 2
    leocar  commented on Feb. 11, 2020, 4:28 p.m.

    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..