The one of Indiana Jones P90688
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
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
- Author
- Ricardo Martín
- Language
- English
- Translator
- Carlos Molina
- Original language
- Spanish
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++