A certain railroad service operates a number of trains between cities in Canada. To save costs, all tracks are ‘one-way’. In other words, a route from Toronto to Montreal does not necessarily mean a route from Montreal to Toronto exists. In fact even if both routes exist, they are distinct and not necessarily the same distance.

Find Train Routes

CanTRainRoutea

Input

You will be given a directed graph where each node represents a town and each edge represents a route between two towns. The weight of each edge represents the distance between two towns. A given route will never appear more than once, and for a given route, the starting and ending town will never be the same.

Image

Learn the Graph Algorithm To Contact

VIVOLEO

Try The Demo
Image

Graph Algorithm Demo

This little APP is to help this railroad service provide customers information about the routes offered. In particular it will solve three types of problems:

   1) compute the distance along a certain route,

   2) count the number of possible routes between two towns and

   3) find the length of the shortest route between two towns.

Image

Output

For test inputs 1 through 5, if no such route exists, output 'NO ROUTE'. Otherwise, walk through the route as given and do not make any extra stops. For example, the first problem means to start at city A, then travel directly to city B (a distance of 5), then directly to city C (a distance of 4).

1. Distance of route A -> B -> C

2. Distance of route A -> D

3. Distance of route A -> D -> C

4. Distance of route A -> E -> B -> C -> D

5. Distance of route A -> E -> D

6. Count the number of trips starting at C and ending at C with a maximum of 3 stops. In the sample data below, there are two such trips: C -> D -> C (2 stops). and C -> E -> B -> C (3 stops).

7. Count the number of trips starting at A and ending at C with exactly 4 stops. In the sample data below, there are three such trips: A to C (via B,C,D); A to C (via D,C,D); and A to C (via D,E,B).

8. The length of the shortest route (in terms of distance) from A to C.

9. The length of the shortest route (in terms of distance) from B to B.

10. The number of different routes from C to C with distance less than 30. In the sample data, these trips are: