ACSU Programming Competition

26 September 1998

Problem 4 - Campus Routes

Description

The largest school on Uranus is the College of Uranus, abbreviated CU. The CU campus is connected with sidewalks. Some of the sidewalks allow students to ride their hovercrafts on them; others allow only pedestrian traffic. Students with hovercrafts must walk with them on pedestrian-only sidewalks.

For example, a map of the CU engineering quad is given on the next page. Pedestrian-only sidewalks are shown with a dashed line; hovercraft sidewalks are shown with a solid line. All sidewalks are two-way.

CU students walk at 5 m/s, and hovercrafts travel at 9 m/s. It takes 7 seconds to mount or dismount the hovercraft. (We really shouldn't be surprised that the Uranoids use the metric system. After all, everybody except the US does.)

CU undergraduates are notoriously late for class. Your job is to determine the fastest route between two points. The students must remain on the sidewalks, and are not allowed to ride their hovercraft on a pedestrian-only sidewalk. The students must begin and end dismounted.

Input

The first line of input will indicate the number of data sets. This number will be non-negative.

The first line of each data set contains three positive integers; call them m, n, and p. m is the number of points in the map, n is the number of paths, and p is the number of routes that you need to determine. The points on the map are labeled beginning with 'A', and proceed consecutively through the alphabet. There are at most 26 points, 50 paths, and 10 routes to be determined.

The next n lines of the data set list the n paths. Each path is given by a pair of points, a length, and a character indicating whether it is a pedestrian-only sidewalk. For example, the lines

A B 25 P
C D 52 H

indicate that there is a path between points A and B, with length 25 meters, and is pedestrian-only; there is also a path between points C and D, with length 52 meters, which allows hovercrafts. Lengths are always positive real numbers.

The next p lines of the data set list the p routes that you need to determine. Each route is given by a pair of points. You are to determine the fastest route between the two points.

Output

At the beginning of each data set, print a message with the data set number.

For each route, print a message with the route number. Then, print the paths to be taken for the route and whether the students is walking or riding, one per line. At the end of the route, print the total time used by the route, with 1 decimal place.

Example

Given the map on the previous page, the fastest route between points A and E is to mount the hovercraft (7 seconds), riding to point B (5 seconds), riding to point F (3.75 seconds), riding to point C (2.5 seconds), riding to point D (5 seconds), dismounting (7 seconds), and walking to point E (10 seconds). The entire route uses 40.25 seconds.

Sample

Sample Input

The comments to the right are not part of the actual input data.

1          Number of data sets.
8 9 2      Beginning of first data set, m = 8, n = 9, p = 2.
A B 40 H   First of 8 paths. Path between A and B is 40 m and allows hovercrafts.
B C 40 P   Second of 8 paths. Path between B and C is 40 m and is pedestrian-only.
B F 30 H
F C 20 H
C D 40 H
D E 50 P
E G 15 P
E H 30 P
H G 20 H   Eighth of 8 paths.
A E        First of 2 routes. What is quickest rout between A and E?
G H        Second of 2 routes.

Sample Output

Data set 1:
Route 1:
  A B riding
  B F riding
  F C riding
  C D riding
  D E walking
Total time 40.3 seconds
Route 2:
  G E walking
  E H walking
Total time 9.0 seconds

Solution

Here is the solution by Mike Smullens in C++.

Here is the test input:

Here is the correct output:

Last updated 28 September 1998.

This page is maintained by Adam Florence. If there are any questions or corrections, please e-mail me.