VIII Olimpiada Informatyczna 2000/2001
|
Task: POD
|
Author: Zbigniew Czech
|
II stage contest, the second day |
Let' us consider a diagram describing a net of municipal transportation, for example a bus-net, tram-net or underground-net etc. Vertices of the diagram
(numbered 1,2,...,n), correspond to stations, edges (pi,pj),
(were pi <>pj) denote
that there is a direct connections from the station
pi to the station pj (1<=pi,
pj<=n). Transportation lines are numbered 1,2,...,k. The transportation line
no. l is defined as a series of stations
pl,1, pl,2,...,pl,sl, on which vehicles of the
line no. l stop, and durations rl,1, rl,2,...,rl,sl-1
of traveling between stations --- rl,1
is the time necessary to get from the station
pl,1 to the station
pl,2, or vice versa (i.e. from the station
pl,2 to the station
pl,1);
rl,2 is the time necessary to get from the station
pl,2 to
pl,3, etc. All the stations of a line are different (i.e. i<>j
implies
pl,i<>pl,j). In the
transportation line no. l vehicles run with certain frequency cl, where
cl
is a number from the set {6, 10, 12, 15, 20, 30, 60}. The vehicles in the
transportation line no. l start from the station
pl,1 at each hour of the day and night, g:0, (0<=g<=23), and than according to the frequency of the line i.e. at
g:cl,g:2cl,... etc. (g:cl means
cl minutes after hour g). Vehicles of the line l
run in two directions: from the station
pl,1 to pl,sl,
and from the station
pl,sl
to
pl,1. The hours of departure of the vehicles of the
transportation line no. l from the station pl,sl
are the same as from the station
pl,1.
In such a transportation net we want to make a trip from the start station x to the finish station
y. We assume that the trip is possible and will take no longer than 24 hours. During the trip one can change
transportation lines as many times as he/she wants to. Say, the time of a change is equal to 0, however, while changing the line we have
to take under consideration the time of waiting for the vehicle that we want to get into. Our
purpose is to get from the start station x, to the finish station y,
as quick as it is possible.
On the picture below you can see a scheme of the transportation net with 6 stations and two lines: no. 1 and no. 2. Vehicles of the line no. 1 go between stations 1, 3, 4 and 6, vehicles of the line no. 2 go between stations 2, 4, 3 and 5. The frequencies with which the vehicles run are equal to c1=15 and c2=20 respectively. The durations of travel between stations are written next to the edges of the net; they are given indices 1 and 2 for particular lines.
Write a program which:
In the first line of the text file POD.IN there are written six integers, separated by single spaces:
The stations are numbered from 1 to n, the transportation lines from 1 to k. In the following 3k lines the transportation lines are described - the description of each of them takes three consecutive lines.
The total number of stations on all transportation lines is not greater than 4000 (i.e. s1+s2+...+sk<=4000).
Your program should write in the only line of the text file POD.OUT two integers, separated by a single space: the hour of the earliest possible arrival to the finish station gy (0<=gy<=23) and the minute of the earliest possible arrival to the finish station my (0<=my<=59).
For the input file POD.IN:
6 2 5 6 23 30 4 15 1 3 4 6 9 12 10 4 20 5 3 4 2 11 17 11the correct answer is the output file POD.OUT:
0 16