Incursión en Espinoscuro

Points: 100 (partial)

Time limit: 4.0s

Memory limit: 1G

Author:

itadrias

Problem type

Allowed languages

C++, Python

El equipo de exploración de Lumbre ha partido al espacio exterior a investigar más a fondo la estructura de Espinoscuro, un planeta hostil y misterioso. Desafortunadamente, el equipo estuvo más tiempo del que debía y fue atacado por unos monstruos. Ahora la nave está rota y para repararla deben buscar ambas balizas de emergencia localizadas en algún lugar del planeta. Por suerte, uno de los miembros de la tripulación había explorado antes este lugar y puede recrear un mapa bastante preciso.

En Espinoscuro hay $N$ ~N~ zonas diferentes. Las zonas están numeradas desde $1$ ~1~ hasta $N$ ~N~. Se sabe que la nave se encuentra en la zona $A$ ~A~, y las dos balizas en las zonas $B$ ~B~ y $C$ ~C~. Además, existen $M$ ~M~ distorsiones que conectan las zonas. Las distorsiones están numeradas desde $1$ ~1~ hasta $M$ ~M~. Existen tres tipos de distorsiones, el tipo de la distorsión $i$ ~i~ ( $1 \le i \le M$ ~1 \le i \le M~) es $X_i$ ~X_i~:

$X_i = 0$ ~X_i = 0~: Son distorsiones bidireccionales que conectan la zona $U_i$ ~U_i~ con la zona $V_i$ ~V_i~. Se pueden cruzar sin ningún costo o restricción adicional, por lo que $W_i = 0$ ~W_i = 0~.
$X_i = 1$ ~X_i = 1~: Son distorsiones unidireccionales que conectan la zona $U_i$ ~U_i~ con la zona $V_i$ ~V_i~. Se pueden cruzar utilizando una cantidad $W_i$ ~W_i~ de suministros de combustible y solo si no se está cargando ninguna baliza.
$X_i = 2$ ~X_i = 2~: Son distorsiones unidireccionales que conectan la zona $U_i$ ~U_i~ con la zona $V_i$ ~V_i~. Se pueden cruzar utilizando una cantidad $W_i$ ~W_i~ de suministros de combustible y solo si se está cargando una baliza.

El equipo de exploración cuenta con un auto inteligente que es capaz de teletransportarse entre las zonas de una distorsión, pero solo si esa distorsión fue transitada antes; teletransportarse entre dos zonas no consume ninguna unidad de combustible.

El miembro que recreó el mapa asegura que la cantidad necesaria de suministros de combustible para cruzar una distorsión de tipo $1$ ~1~ o $2$ ~2~ no excederá de $K$ ~K~.

Una secuencia de zonas $v_0, v_1, \ldots, v_k$ ~v_0, v_1, \ldots, v_k~ (para $k \ge 0$ ~k \ge 0~) es un camino si para cada par de zonas consecutivas $v_l$ ~v_l~ y $v_{l+1}$ ~v_{l+1}~ (para cada $l$ ~l~ tal que $0 \le l < k$ ~0 \le l < k~) son adyacentes. Un camino $v_0, v_1, \ldots, v_k$ ~v_0, v_1, \ldots, v_k~ conecta las zonas $v_0$ ~v_0~ y $v_k$ ~v_k~.

El equipo de exploración debe asegurarse de traer una baliza a la vez hasta la nave, es decir, ir por un camino desde la zona donde está ubicada la nave hasta la zona donde está ubicada la primera baliza, y regresar por un camino desde la zona donde está ubicada la primera baliza hasta la zona donde está ubicada la nave; luego repetir este mismo proceso con la segunda baliza.

Debido a que los suministros de combustible son escasos, los exploradores te solicitan que calcules la mínima cantidad de suministros de combustible que deben gastar para reparar la nave y salir de Espinoscuro.

Entrada

La primera línea contiene un entero $T$ ~T~ $-$ ~-~ la cantidad de casos de prueba a procesar.

A continuación se describe el formato de cada caso de prueba:

La primera línea contiene tres enteros $N$ ~N~, $M$ ~M~ y $K$ ~K~ $-$ ~-~ la cantidad de zonas en Espinoscuro, la cantidad de distorsiones que las conectan y la máxima cantidad de suministros de combustible necesaria para cruzar una distorsión de tipo $1$ ~1~ o $2$ ~2~, respectivamente.
La segunda línea contiene tres enteros $A$ ~A~, $B$ ~B~ y $C$ ~C~ ( $1\le A, B, C\le N$ ~1\le A, B, C\le N~) $-$ ~-~ los índices de las zonas donde se encuentran la nave y las dos balizas, respectivamente.
Le siguen $M$ ~M~ líneas, la $i$ ~i~-ésima de esas líneas contiene cuatro enteros $X_i$ ~X_i~, $U_i$ ~U_i~, $V_i$ ~V_i~ y $W_i$ ~W_i~ $-$ ~-~ la descripción de la distorsión $i$ ~i~ ( $1 \le i \le M$ ~1 \le i \le M~).

Salida

La salida debe contener $T$ ~T~ líneas $-$ ~-~ la línea $i$ ~i~ debe contener la mínima cantidad de suministros de combustible que deben gastar para reparar la nave y salir de Espinoscuro, o $-1$ ~-1~ en caso de que no se pueda cumplir con ese objetivo.

Restricciones

$1 \le T \le 7$ ~1 \le T \le 7~
$1 \le N \le 10^5$ ~1 \le N \le 10^5~
$1 \le M \le 4 \cdot 10^5$ ~1 \le M \le 4 \cdot 10^5~
$1 \le K \le 5$ ~1 \le K \le 5~
$1 \le A, B, C \le N$ ~1 \le A, B, C \le N~
$X_i \in \{0, 1, 2\}$ ~X_i \in \{0, 1, 2\}~ para cada $i$ ~i~ tal que $1\le i \le M$ ~1\le i \le M~
$1 \le U_i, V_i \le N$ ~1 \le U_i, V_i \le N~; $U_i \neq V_i$ ~U_i \neq V_i~ para cada $i$ ~i~ tal que $1 \le i \le M$ ~1 \le i \le M~
Si $X_i = X_j$ ~X_i = X_j~ entonces $(U_i, V_i) \neq (U_j, V_j)$ ~(U_i, V_i) \neq (U_j, V_j)~ para cada $i$ ~i~ y $j$ ~j~ tal que $1 \le i < j \le M$ ~1 \le i < j \le M~
$W_i = 0$ ~W_i = 0~ para cada $i$ ~i~ tal que $1 \le i \le M$ ~1 \le i \le M~ y $X_i = 0$ ~X_i = 0~
$1 \le W_i \le K$ ~1 \le W_i \le K~ para cada $i$ ~i~ tal que $1 \le i \le M$ ~1 \le i \le M~ y $X_i \in \{1, 2\}$ ~X_i \in \{1, 2\}~

Subtareas

Subtarea	Restricciones Adicionales	Puntos	Dependencias
$1$ ~1~	$A = C$ ~A = C ~	$7$ ~7~	$-$ ~-~
$2$ ~2~	$T = 1$ ~T = 1~; $N \le 250$ ~N \le 250~	$8$ ~8~	$-$ ~-~
$3$ ~3~	$N \le 250$ ~N \le 250~	$15$ ~15~	$2$ ~2~
$4$ ~4~	$T = 1$ ~T = 1~	$20$ ~20~	$2$ ~2~
$5$ ~5~	$K \le 1$ ~K \le 1~	$20$ ~20~	$-$ ~-~
$6$ ~6~	$-$ ~-~	$30$ ~30~	$1-5$ ~1-5~

Ejemplos

Entrada 1

Salida 1

La nave se encuentra en $1$ ~1~ y las balizas en las dos zonas restantes, por lo que se puede:

Viajar a la zona $3$ ~3~ utilizando dos unidades de combustible y recoger la baliza.
Volver a la zona $1$ ~1~ utilizando tres unidades de combustible y dejar la baliza en la nave.
Viajar a la zona $2$ ~2~ sin emplear unidades de combustible y recoger la baliza.
Volver a la zona $1$ ~1~ sin emplear unidades de combustible y dejar la baliza en la nave.

El gasto total de combustible sería $2 + 3 = 5$ ~2 + 3 = 5~.

Entrada 2

Salida 2

CC BY 4.0

Comments

There are no comments at the moment.