# Rutas con peajes Una empresa de transporte reparte entre ciudades unidas por carreteras. Algunas carreteras tienen peaje. Para cada viaje, el contrato con el cliente fija cuántos peajes puede pagar el camión como máximo, y el despacho quiere saber cuántos kilómetros recorrerá en la ruta más corta que respete ese límite. Todas las carreteras son de doble sentido. Pasar por una carretera con peaje cuenta como un peaje cada vez que se pasa, en cualquier sentido. Una ruta puede repetir ciudades, si eso le conviene. ## Entrada La primera línea tiene tres enteros: n, la cantidad de ciudades, numeradas de 0 a n − 1; m, la cantidad de carreteras; y k, el máximo de peajes del viaje. La segunda línea tiene dos enteros: s, la ciudad de salida, y t, la de llegada. Pueden ser la misma. Cada una de las m líneas siguientes describe una carretera con cuatro enteros a, b, w y p: une las ciudades a y b, mide w kilómetros, y tiene peaje si p = 1 o no lo tiene si p = 0. Entre dos ciudades puede haber varias carreteras. Ninguna carretera une una ciudad consigo misma. ## Salida Una línea con un entero: los kilómetros de la ruta más corta de s a t con a lo sumo k peajes, o -1 si no hay ninguna ruta así. ## Límites - 1 ≤ n ≤ 50 000 - 0 ≤ m ≤ 100 000 - 0 ≤ k ≤ 20 - 0 ≤ s, t < n - 1 ≤ w ≤ 1 000 000 000 - a ≠ b ## Ejemplo Entrada: ```text 5 6 1 0 4 0 1 2 1 1 4 3 1 0 2 3 0 2 1 4 0 2 3 6 0 3 4 5 1 ``` Salida: ```text 10 ``` La ruta 0, 1, 4 mide solo 5 kilómetros, pero pasa por dos peajes, y este viaje permite uno. La mejor con un peaje es 0, 2, 1, 4, que mide 3 + 4 + 3 = 10. La ruta 0, 2, 3, 4 también tiene un solo peaje, y mide 14. ## Para pensar antes de programar En el ejemplo, la forma más corta de llegar a la ciudad 1 mide 2 kilómetros, y la ciudad 1 está en la mejor ruta hasta la 4. Aun así, esa ruta llega a la ciudad 1 después de 7 kilómetros. ¿Por qué? ¿Qué respondería un programa que recuerda solo la menor distancia de cada ciudad? Escriban un caso propio de 4 ciudades, distinto del de los apuntes, en el que ese programa diga -1 y sí exista una ruta. Agréguenlo a su carpeta de pruebas. ## Tiempo 2 segundos por caso, compilado con `-O2`. Corran `make test` para probar con el juez. Algunos casos grandes no se guardan: `casos/gen_NN.cpp` los escribe al correr `make test`. ## Extensión Sin casos en el juez, para seguir pensando: cambien el contrato. Ya no hay límite de peajes, y el despacho tiene un solo cupón que deja gratis, con 0 kilómetros contados, una carretera a elección. ¿Cuál es la distancia mínima de s a t? Usen la misma forma de razonar, y comparen su respuesta con una búsqueda exhaustiva en redes pequeñas.