El de Indiana Jones P90688
Indiana Jones tiene que transportar las joyas y reliquias que ha robado del templo maldito por la jungla hasta el aeropuerto, para llevarlas a los museos de todo Occidente. Sin embargo apenas tiene gasolina en su camión para recorrer K kilómetros. Indiana sabe que las carreteras de la zona tienen muchos puentes que aguantan el peso de su camión por poco. Por ello no puede cargar todas las joyas que él quisiera. Indiana sabe la distancia de cada camino entre dos pueblos de la zona y el peso máximo que aguantan los puentes del camino. Las carreteras más cortas son las que suelen tener los puentes más débiles. El aeropuerto está en el pueblo llamado Wagamama. Calcula el peso máximo de tesoro que Indiana puede llevar en su camión, sabiendo que este pesa C kilos.
Entrada
La entrada consistirá en varios casos de prueba, indicándose el número de estos en la primera línea de la entrada. Cada caso empezará con una línea donde se indicará el número 1≤ M≤ 10000 de caminos del mapa, el nombre de la ciudad dónde está Indiana Jones al volver del templo maldito, la cantidad 1≤ K≤ 100000 de kilómetros que Indiana puede recorrer con la gasolina que le queda y el peso 1≤ C≤ 10000 del camión (incluyendo a Indiana). En las siguientes M líneas se indicarán para cada camino, las dos ciudades que tiene a sus extremos separadas por un espacio, la longitud del camino en kilómetros y el peso máximo que aguantan sus puentes. Los nombres de las ciudades serán cadenas de letras mayúsculas y minúsculas sin más símbolos extraños. En el mapa que tiene Indiana Jones no hay más de 500 ciudades y las longitudes de cada camino son menores de 1000 kilómetros.
Fijaos (ved los casos de prueba de ejemplo) que las carreteras son bidireccionales, y que para cada par de ciudades A y B, puede haber cero, un o más de un camino que las una directamente.
Salida
Para cada caso de prueba, escribe una línea que diga el peso máximo del tesoro en kilos y, para esa cantidad de tesoro, la distancia mínima en kilómetros que tendría que recorrer para llegar al aeropuerto. Si Indiana no pudiera llegar hasta Wagamama con la gasolina que le queda siguiendo los caminos del mapa, o si pudiese llegar pero con una carga de tesoro efectiva de 0 kilos, escribe ’Indiana se queda sin tesoro.’ (respetando mayúsculas y minúsculas y el punto final).
Puntuación
- TestA: Pruebas donde todos los puentes pueden soportar el mismo peso. 40 Puntos
- TestB: Pruebas donde en ningún mapa aparecen más de 100 ciudades. 35 Puntos
- TestC: Pruebas de todo tipo. 25 Puntos
Input
3 5 Patacoma 15 1200 Patacoma Watapito 10 8000 Watapito Wagamama 6 6000 Patacoma Wogopote 5 6500 Watapito Wogopote 4 7000 Wogopote Wagamama 12 10000 1 Patagama 15 6000 Patagama Wagamama 20 10000 1 Patagama 15 1000 Patagama Wagamama 10 1000
Output
4800 15 Indiana se queda sin tesoro. Indiana se queda sin tesoro.
Input
6 1 Waga 10 1000 Waga Wagamama 10 1000 1 Waga 10 5000 Wagamama Waga 10 10000 3 Waga 40 5000 Waga Wagaba 10 6000 Wagaba Wagaca 10 7000 Wagada Wagamama 10 7000 3 Waga 17 1000 Waga Wagamama 10 2000 Wagamama Waga 20 3000 Waga Wagamama 30 2000 5 Wama 37 1165 Wama Wamaba 98 1978 Wama Wamaca 56 1942 Wama Wamada 96 1122 Wamaba Wamaca 97 1565 Wamaca Wamada 71 1822 6 Wama 141 1152 Wama Wamaca 31 1997 Wama Wamada 82 1532 Wama Wamaba 67 1761 Wamaba Wagamama 73 1892 Wamaca Wamada 55 1651 Wamaca Wagamama 39 1570
Output
Indiana se queda sin tesoro. 5000 10 Indiana se queda sin tesoro. 1000 10 Indiana se queda sin tesoro. 609 140
- Author
- Ricardo Martín
- Language
- Spanish
- Other languages
- English
- Official solutions
- C++
- User solutions
- C++