The one of Indiana Jones P90688


Statement
 

pdf   zip

thehtml

Indiana Jones has to carry the jewellery and relics that has stolen from the temple of doom trough the jungle to the airport, to bring them to the different occident museums. However, he barely has fuel in his lorry to cover K kilometres. Indiana knows that the roads of the area have a lot of bridges that take the weight of the lorry by few. For this reason he cannot load all the jewellery that he would like. Indiana knows the distance of each path between two villages of the area and the maximal weight that the bridges of the path take. The shorter roads used to have the weaker bridges. The airport is in the town called Wagamama. Compute the maximal weight of treasure than Indiana can load in his lorry, knowing that its weight is C kilos.

Input

The input will consist of various test data, indicating the number of these in the first line of the input. Each case will start with a line where will be indicated the number 1≤ M≤ 10000 of paths of the map, the name of the city where Indiana Jones is coming back from the temple of doom, the quantity 1≤ K≤ 100000 of kilometres that Indiana can cover with the fuel that his lorry has and its weight 1≤ C≤ 10000 (counting Indiana). The following M lines will be indicated for each path, the two cities that has in its extremes separated by a space, the length of the path in kilometres and the maximal path that their bridges take. The names of the cities will be strings of upppercase and lowercase letters without any strange symbols. In the maps that Indiana Jones has there are not more than 500 cities and the lenghts of each path are less than 1000 kilometres.

Notice (look the test data of instance) that the roads are bidirectional, and that for each pair of cities A and B, can be zero, one or more than a path that link directly.

Output

For each test data, your program must print a line that indicates the maximal weight of the treasure in kilos and, for this quantity of treasure, the minimal distance in kilometres that he would have to cover to arrive to the airport. If Indiana could not arrive to Wagama with the fuel that he has following the paths of the map, or if he could arrive but with a load of treasure of 0 kilos, it must print ’Indiana has no treasure.’ (respecting uppercase and lowecarse letters and the final dot).

Scoring

  • TestA:  ‍ Tests where all the bridges can take the same weight.  ‍40 Points ‍
  • TestA:  ‍ Tests where in any map appears more than 100 cities.  ‍35 Points ‍
  • TestA:  ‍ Tests of all kinds.  ‍25 Points ‍
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 has no treasure.
    Indiana has no treasure.
    
  • 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 has no treasure.
    5000 10
    Indiana has no treasure.
    1000 10
    Indiana has no treasure.
    609 140
    
  • Information
    Author
    Ricardo Martín
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++