El de Indiana Jones P90688


Statement
 

pdf   zip

thehtml

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 ‍
Public test cases
  • 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
    
  • Information
    Author
    Ricardo Martín
    Language
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++