It is well known that the Moon of Valencia is magical. Everyone talks about a mystery that happens at night. People remember what time they entered the first bar, what time arrived to the hotel and how happy they arrived, but nobody remembers the bars and pubs they visited. The Valencia hotels have hired you for developing an application that helps customers to remember. The application will inform customers with one of all the possible sequences of bars and pubs. Customers have to provide the following information: departure time and place, arrival time and place, and degree of satisfaction on arrival. The application uses a map with the location of each bar or pub. Each bar or pub produces a different degree of satisfaction when visited. But people gets angry when walks from one place to another, that’s the reason why walking between different places reduces the degree of satisfaction. The reduction considered depends on the amount of minutes people needs to get one place from another one. If the amount of minutes is not an integer the remaining seconds should be considered a portion of a minute, i.e., 30 seconds imply 0.5 minutes. People walk at a speed of 4 km/h, can stay in a bar or pub the time they like, but for getting the satisfaction must remain at least 15 minutes. People can decide not to visit a bar or pub, i.e., they can use a path from the origin to the target and to enter in a subset of all the bars or pubs reachable with the path. Entering to the departure place is optional, like entering others places. The goal grade of satisfaction is computed up to the door of the target place, without entering it. So the grade of satisfaction of the target place (bar, pub or hotel) should not be computed. Input Input consists of several test cases. Each case begins with the map description, which is followed by the list of arrivals your application have to check. The description of a map begins with the word ‘MAP’ in capital letters followed by two integer numbers, P and M, where P is the number of places and M is the number of paths connecting two places. (1 ≤ P ≤ 64). Places and paths are described one per line. Each place is described with two coordinates (real numbers represent kilometers), its grade of satisfaction (a real number), the ID and the name. The paths connecting two places are identified by the their identifiers. Each pair of places can only be connected by one path. Figure 1 shows the map corresponding to the first map in the example input case. It is guaranteed that no crossing paths exist. The list of arrivals to be processed begins after a line with the word ‘ARRIVALS’ in uppercase. Each arrival is described in a single line, including departure time, departure place, arrival time, arrival place and the grade of satisfaction on arrival, a real number. Output The output for each case must begin with the word ‘MAP’ in capital letters followed by anumber indicating the number of test case. The first test case is ‘MAP 1’, second is ‘MAP 2’, and so on. For each arrival proposed in the input it must appear a line in the output specifying a valid path found or the string ‘Impossible!’ indicating that it is not possible to find a path from origin to target with the required grade of satisfaction. A path found will be valid if the absolute difference between the required grade of satisfaction and the obtained one is less than 0.1, and contains no loops, i.e. a place can’t appear in the path found more than once.
2/5 Figure 1: Representation of the first map in the input example. Eachpathfoundmustbeginwiththestring‘PATH FOUND:’incapitalletters,followedbytheobtained grade of satisfaction with three decimal digits and then the sequence of places from origin up to target. The ID of the unvisited places must appear preceded by the ‘!’ sign. Noticeas the ID of the target place never is preceded by this sign. Hint: Set up your solution for running as fast as possible by using this example, it should be enough for all test cases. Sample Input MAP 19 40 0 0 5 5 0 1 1.1 1 0 UPV Universitat Politecnica de Valencia 0 SPV Contest hotel 35 B01 The Object 42 B02 Opera 0.6 1.7 33 B03 New York
3/5 1.3 2 55 B04 Blue Note 1.5 2.5 23 B05 The Popes 2.5 2 13 B06 Petrol 4 3.5 12 B07 King of Kings 1.1 4 14 B08 O Salati 1.2 4.5 13 B09 The Snails 2.5 3.5 34 B10 The Earth 1.5 1.5 55 B11 Cafe Coffee 3 4.5 31 B12 Vermouth house 4.5 2.5 45 B13 Jamon Session 1.3 3.6 24 B14 Let’s go to eat 1.5 4 34 B15 I’m hungry 0.6 2.5 53 B16 The Gecko 3.5 2.5 43 B17 The Black Sheep UPV B01 B01 B02 B01 B03 B01 B16 B02 B03 B02 B11 B16 B08 B16 B14 B16 B03 B03 B04 B03 B11 B04 B11 B04 B16 B04 B05 B05 B14 B08 B09 B08 B15 B08 B14 B11 B06 B14 B15 B05 B06 B05 B16 B05 B10 B15 B09 B15 B10 B09 B12 B06 B10 B06 B17 B10 B07 B10 B17 B10 B12 B10 B14 B12 B15 B12 B07 B12 SPV B17 B07
4/5 B17 B13 B07 B13 B07 SPV B13 SPV ARRIVALS 23:00 UPV 03:00 SPV 9.0 23:00 UPV 03:00 SPV 8.0 23:00 UPV 03:00 SPV 7.0 23:00 UPV 03:00 SPV 6.0 23:00 UPV 03:00 SPV 5.0 23:00 UPV 03:00 SPV 4.0 23:00 UPV 03:00 SPV 3.0 23:00 UPV 03:00 SPV 2.0 23:00 UPV 03:00 SPV 1.0 23:00 UPV 03:00 SPV 0.0 23:00 UPV 03:00 SPV -1.0 23:00 UPV 03:00 SPV -2.0 23:00 UPV 03:00 SPV -30.0 23:00 UPV 03:00 SPV -40.0 23:00 B05 03:00 B10 40.0 23:00 B05 03:00 B10 30.0 23:00 B05 03:00 B10 20.0 23:00 B05 03:00 B10 10.0 23:00 B05 03:00 B10 0.0 23:00 B05 03:00 B10 -10.0 23:00 B05 03:00 B10 -20.0 23:00 B05 03:00 B10 -30.0 23:00 B05 03:00 B10 -40.0 MAP 2 1 0 0 0 UPV Universitat Politecnica de Valencia 10 10 0 SPV Hotel Silken Puerta de Valencia UPV SPV ARRIVALS 23:00 UPV 1:00 SPV 9.0 23:00 UPV 1:00 SPV 8.0 Sample Output MAP 1 PATH FOUND: 9.002 UPV B01 B16 B04 !B11 B06 !B17 !B13 SPV PATH FOUND: 7.929 UPV B01 B16 B14 B08 B09 !B12 SPV PATH FOUND: 6.973 UPV B01 B16 B04 !B11 B06 !B10 !B07 SPV PATH FOUND: 6.028 UPV B01 B16 B05 B10 !B17 !B07 SPV PATH FOUND: 4.995 UPV B01 B16 B04 !B05 !B14 !B15 !B10 B07 SPV PATH FOUND: 4.078 UPV B01 B16 B08 !B15 B12 B07 SPV PATH FOUND: 3.028 UPV B01 B16 B05 !B10 B12 !B07 SPV PATH FOUND: 1.929 UPV B01 B16 B14 !B15 B08 B09 !B12 SPV PATH FOUND: 0.912 UPV B01 B16 B03 !B04 !B05 !B06 B17 !B13 !B07 SPV PATH FOUND: 0.028 UPV B01 B16 B05 !B10 B17 !B13 !B07 SPV PATH FOUND: -0.986 UPV B01 B16 B08 !B09 !B15 B12 SPV PATH FOUND: -1.973 UPV B01 B16 B03 !B04 !B05 B10 !B17 !B07 SPV
5/5 PATH FOUND: -29.953 UPV B01 B03 !B16 B05 !B10 !B14 B15 !B12 SPV PATH FOUND: -39.913 UPV B01 B03 !B16 B08 !B09 !B15 B12 !B07 SPV PATH FOUND: 40.069 B05 B16 B14 !B08 B09 !B15 B10 PATH FOUND: 30.012 B05 B16 B08 !B15 B10 PATH FOUND: 19.979 !B05 B04 !B03 B02 !B01 B16 !B08 !B09 !B15 B10 PATH FOUND: 10.004 B05 B14 B08 !B15 !B09 B12 B10 PATH FOUND: 0.004 !B05 B14 B08 !B15 B09 B12 B10 PATH FOUND: -9.966 B05 !B14 !B15 B12 B10 PATH FOUND: -20.012 B05 !B06 !B17 B07 B12 B15 !B14 B10 PATH FOUND: -30.012 !B05 B06 !B17 B07 B12 B15 !B14 B10 PATH FOUND: -40.018 !B05 !B04 !B16 B14 !B15 B10 MAP 2 Impossible! Impossible!