
VIII Olimpiada Informatyczna 2000/2001

Task: POD

Author: Zbigniew Czech

Travel
II stage contest, the second day 

Let' us consider a diagram describing a net of municipal transportation, for example a busnet, tramnet or undergroundnet etc. Vertices of the diagram
(numbered 1,2,...,n), correspond to stations, edges (p_{i},p_{j}),
(were p_{i} <>p_{j}) denote
that there is a direct connections from the station
p_{i} to the station p_{j} (1<=p_{i},
p_{j}<=n). Transportation lines are numbered 1,2,...,k. The transportation line
no. l is defined as a series of stations
p_{l,1}, p_{l,2},...,p_{l,sl}, on which vehicles of the
line no. l stop, and durations r_{l,1}, r_{l,2},...,r_{l,sl1}
of traveling between stations  r_{l,1}
is the time necessary to get from the station
p_{l,1} to the station
p_{l,2}, or vice versa (i.e. from the station
p_{l,2} to the station
p_{l,1});
r_{l,2} is the time necessary to get from the station
p_{l,2} to
p_{l,3}, etc. All the stations of a line are different (i.e. i<>j
implies
p_{l,i}<>p_{l,j}). In the
transportation line no. l vehicles run with certain frequency c_{l}, where
c_{l}
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
p_{l,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:c_{l},g:2c_{l},... etc. (g:c_{l} means
c_{l} minutes after hour g). Vehicles of the line l
run in two directions: from the station
p_{l,1} to p_{l,sl},
and from the station
p_{l,sl}
to
p_{l,1}. The hours of departure of the vehicles of the
transportation line no. l from the station p_{l,sl}
are the same as from the station
p_{l,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.
Example
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
c_{1}=15 and
c_{2}=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.
Let us assume, that at 23:30 we stay on the station no. 5 and we want to get to the
station
no. 6. It is necessary to wait 10 minutes and then (at 23:40) one can leave using line no. 2. There are two options of our trip. The first option is to get to the station
no. 3 at 23:51, wait 3 minutes, change to the line no. 1 at 23:54 and get to the station 6 at
0:16 (the next day). The second option is to take the line no. 2 and get to
the station no. 4 at 0:8 a.m., we wait 13 minutes and at 0:21 a.m. we take the vehicle
of the line no. 1 and we get to the station no. 6 at 0:31. Thus the earliest
time we can get to the station no. 6 is at 0:16.
Task
Write a program which:

reads from the text file POD.IN the description of the transportation
net, transportation lines, number of the start station x, number of the finish
station y, the hour and minute of the beginning of the trip 
g_{x}
and m_{x }respectively,

finds the shortest time of the trip from the start station x to the finish station
y,

writes to the text file POD.OUT the earliest possible time of getting to the finish station
y  g_{y}
and m_{y }(hour and minute respectively).
Input
In the first line of the text file POD.IN there are written six integers, separated by single spaces:

the number of stations n (1<=n<=1000),

the number of lines k (1<=k<=2000),

the number of the start station x (1<=x<=n),

the number of the finish station y (1<=y<=n),

the hour of the beginning of the trip g_{x} (0<=g_{x}<=23),

the minute of the beginning of the trip m_{x} (0<=m_{x}<=59).
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.

In the first line describing the transportation line no. l there are written two integers, separated by a single space:
s_{l}, the number of stations (2<=s_{l}<=n), and
c_{l}  the frequency with which the vehicles run
(c_{l} belongs to: {6, 10, 12, 15, 20, 30, 60}).

In the second line describing the transportation line no. l there are
s_{l} different integers, separated by single spaces:
p_{l,1},p_{l,2},...,p_{l,sl}
 the numbers of consecutive stations on the transportation line no. l
(1<=p_{l,i}<=n, for 1<=i<=s_{l}).

In the third line describing the transportation line no. l there are written s_{l}1 integers separated by single spaces:
r_{l,1}, r_{l,2},..., r_{l,sl1}
 the times (in minutes) necessary to go between the
consecutive stations of this transportation line (1<=r_{l,i}<=240,
for 1<=i<=s_{l}1).
The total number of stations on all transportation lines is not greater than 4000 (i.e.
s_{1}+s_{2}+...+s_{k}<=4000).
Output
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
g_{y} (0<=g_{y}<=23) and the minute of
the earliest possible arrival to the finish station
m_{y} (0<=m_{y}<=59).
Example
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 11
the correct answer is the output file POD.OUT:
0 16
Print friendly version
