Not an official ACM page
[Problem E | 1995 Regional problem set | My ACM problem archive | my home page]

Problem D -- Non-Stop Travel -- Filename `NONSTOP`

David hates to wait at stop signs, yield signs and traffic signals while driving. To minimize this aggravation, he has prepared maps of the various regions in which he frequently drives, and measured the average delay (in seconds) at each of the various intersections in these regions. He wants to find the routes between specified points in these regions which minimize his delay at intersections (regardless of the total distance he has to drive to avoid delays), and has enlisted your assistance in this effort.

Input

For each region, David provides you with a map. The map data first identifies some number of intersections, NI. The regions never include more than 10 intersections. The intersections in each region are numbered sequentially, starting with the number one (1). For each intersection, in turn, the input then specifies the number of streets leading away from the intersection, and for each such street, the number of the intersection to which the street leads, and the average delay, in seconds, that David encounters at that intersection. Following the data for the last intersection in a region there appear the numbers associated with the intersections where David wants to start and end his drive. The entire input consists of a sequence of maps, followed by the single integer zero (0).

Output

For each region, in order, print a single line of output which contains the region number (they, too, are sequentially numbered, starting with 1), a list of the intersection numbers David will encounter in the route with minimum average delay, and the average number of seconds he will be delayed while travelling this route. A suitable format is shown in the example below, but other similar output styles are acceptable.

Notes

There will always be a unique route with the minimum average delay in each region.
A street from intersection I to intersection J is one-way. To represent a two-way street from I to J, the map must also include a route from intersection J to intersection I.
There will never be more than one route directly from intersection I to intersection J.

Example

Suppose David wants to travel from intersection 2 to intersection 4 in the region shown in the following map:


	+---------------+                   From To Delay
	|               V                     1   3   3
	1<------2------>3------>4<------5     1   4   6
	|       |               ^       ^     2   1   2
	|       +---------------|-------+     2   3   7
	|                       |             2   5   6
	+-----------------------+             3   4   5
                                              5   4   7

The input and output for this example is shown as the first case in the Example Input and Expected Output shown on the next page.

Sample solution
Example Input

5
2  3 3   4 6
3  1 2   3 7   5 6
1  4 5
0
1  4 7
2 4

2
1   2 5
1   1 6
1 2

7
4   2 5   3 13
    4 8   5 18
2   3 7   6 14
1   6 6
2   3 5   5 9
3   6 2   7 9
    4 6
1   7 2
0
1 7

0

Expected Output

Case 1: Path = 2 1 4; 8 second delay
Case 2: Path = 1 2; 5 second delay
Case 3: Path = 1 2 3 6 7; 20 second delay

This page maintained by Ed Karrels.
Last updated September 20, 1999

Problem D -- Non-Stop Travel -- Filename NONSTOP