Traffic jam is one of the major concerns of Dhaka city. Lately this has been realized through some desperate measures taken by the government. While the actions taken reduce traffic jams, they do create some unwanted problems as well. Take for example the latest ban on non-motorize vehicles on an important road of Dhaka. It certainly has reduced jams in that region, but people are having trouble to get a reasonable means for transportation. After analyzing the present situation we came to know that some people would like to find the fastest way with the cheapest cost, and some would like to find the cheapest route with the fastest time. They may sound similar – for some certain route they are the same too. But this is not always true. We’d like to hire you to solve the problem for both the group so that they can learn to do some trade-off. You have been told to solve the problem in a smaller scale at first. You’re provided with the following information: • There will be at most 100 intersections. Intersections are numbered by integers: 0,1,2,... • There can be many roads and/or many routes in between two intersections. • All the roads are bidirectional. And none of them are longer than 20 km. • Roads are classified into three categories: – Open for motorized vehicles only – Open for non-motorized vehicles only – Open for all types of vehicles • Vehicles are classified into two groups: – Motorized – Non-motorized • You need to be concerned with the following vehicles only: Name Type Average Speed Minimum Fare Fare for fur- ther travel Availability (wait for) Rickshaw Non-motorized 10 kmph 5 Tk for first 1 km 2 Tk per km 2 min Auto- Rickshaw Motorized 30 kmph 20 Tk for first 2 km 10 Tk per km 3 min Taxi-Cab Motorized 50 kmph 20 Tk for first 2 km 16 Tk per km 10 min Bus Motorized 40 kmph 2 Tk for first 5 km 1 Tk per km 30 min • You cannot get down or get into a vehicle from anywhere other than the intersections. • The drivers would never accept fractional fares. And they’re not willing to accept anything less than what they deserve. However, they wouldn’t object if you’re willing to pay extra.
2/3 Input There will be multiple test cases. The first line of a test case will give you N and M, N is the number of intersections in the city, 0 < N < 101. M is the number of road descriptions. 0 < M ≤ N ∗ N. The second line would give you u and v, source and destination intersection respectively. The following M line will give the description in the following format. U V DISTANCE TYPE U, V are integers < N. DISTANCE is an integer < 21, the unit is kilo-meters. TY PE can be: ‘N’ for Non-motorized, ‘M’ for Motorized, and ‘A’ for all types of vehicle. Output For each test case, give three lines of output. The first line would contain the test case number in the form ‘Case#n, n = 1, 2, . . .. The next line would contain, travel fare followed by the travel time in the fastest route. No other route should be faster than this one, in case of a tie choose the one with least expense. Similarly, the third line would contain the travel fare followed by the travel time in the cheapest route. No other route should be cheaper than this, in case of a tie ... you guessed it ... choose the fastest one. The travel fare is an integer, and the travel time measured in minutes, is a real number rounded to 2 decimal places. These two numbers in each line should be separated by a single space. If the destination is unreachable from the source print the word ‘UNREACHABLE’ without quotes in both the lines. Sample Input 5 10 01 0 1 10 N 0 2 11 A 0 3 14 M 042M 121N 136N 1 4 13 N 237M 2 4 19 N 3 4 12 A 24 10 0 1 10 N 0 1 11 M 0 1 12 A 0 1 13 N 34 12 0 1 10 N 0 1 11 M 0 1 12 A 0 1 13 N
3/3 33 02 0 1 10 N 122M 121N 32 02 0 1 10 N 121M Sample Output Case#1 169 31.20 13 54.50 Case#2 164 23.20 8 46.50 Case#3 UNREACHABLE UNREACHABLE Case#4 25 68.00 25 68.00 Case#5 43 67.00 25 93.50