Vladimir has white skin, very long teeth and is 600 years old, but that's not a problem because Vladimir is a vampire. It's a good life, much less problematic than one would imagine it to be. In fact, Vladimir is a successful doctor who always takes the night shift, which makes him a valued member of the team. Also, he has an impressive trick which he loves to show at dinner parties: he can tell blood group by taste. Moderately disturbing, drunk people still love to see that.
Anyway, what Vladimir also likes is traveling, but being a vampire he most overcome three problems:
He can only travel by train, because he must take his coffin with him. Fortunately, he can always travel first class because he has made a lot of money through... Well, you don't want to know, really.
He can only travel from dusk till dawn, namely, from 6 P.M. to 6 A.M. During the day he has to stay inside a train station to avoid obliteration.
He has to take something to eat with him. He needs one litre of blood per day, which he drinks at noon (12:00) inside his coffin.
Help Vladimir to find the shortest route between two given cities, so that he can travel with the minimum amount of blood. If he takes too much with him, people ask questions, and making them disappear is not exactly what he likes to do in his spare time.
The first line of the input will contain a single number telling you the number of test cases.
Each test case specification begins with a single number telling you how many route specifications follow. Each route specification consists of the names of two cities, the departure time from city one, and the total traveling time, with all times in hours. Remember, Vladimir cannot use routes departing earlier than 18:00 or arriving later than 6:00.
There will be at most 100 cities and less than 1,000 connections. No route takes less than 1 hour or more than 24 hours, but Vladimir can only use routes within the 12 hours travel time from dusk till dawn.
All city names are at most 32 characters long. The last line contains two city names. The first is Vladimir's start city; the second is Vladimir's destination.
For each test case you should output the number of the test case followed by either
Vladimir needs # litre(s) of blood. or
There is no route Vladimir can take.
2 3 Ulm Muenchen 17 2 Ulm Muenchen 19 12 Ulm Muenchen 5 2 Ulm Muenchen 10 Lugoj Sibiu 12 6 Lugoj Sibiu 18 6 Lugoj Sibiu 24 5 Lugoj Medias 22 8 Lugoj Medias 18 8 Lugoj Reghin 17 4 Sibiu Reghin 19 9 Sibiu Medias 20 3 Reghin Medias 20 4 Reghin Bacau 24 6 Lugoj Bacau
Test Case 1. There is no route Vladimir can take. Test Case 2. Vladimir needs 2 litre(s) of blood.
Please log in to submit your solution.
|Average test runtime||0.30|
|Points (changes over time)||10|
|Tried by||3 users|
|Solved by||2 users|