|
|
VIII Olimpiada Informatyczna 2000/2001
|
|
Zadanie: POD
|
Autor: Zbigniew Czech
|
Podróż
| Zawody II stopnia, dzień drugi |
8 luty 2001
|
| Plik źródłowy: | POD.??? (np. pas, c, cpp) |
| Plik wykonywalny: | POD.exe |
| Plik wejściowy: | POD.in |
| Plik wyjściowy: | POD.out |
Rozważmy graf opisujący sieć komunikacji publicznej,
np. sieć autobusową, tramwajową, metra, itp.
Wierzchołki grafu, o numerach 1,2,...,n, reprezentują
przystanki, a krawędzie (pi,pj),
(dla pi <>pj)
oznaczają możliwe, bezpośrednie przejazdy od przystanku pi do
pj (1<=pi, pj<=n).
W sieci kursują pojazdy linii komunikacyjnych.
Linie komunikacyjne oznaczone są numerami 1,2,...,k.
Linia komunikacyjna l zdefiniowana jest przez ciąg przystanków
pl,1, pl,2,...,pl,sl,
przez które przejeżdżają pojazdy linii, oraz czasy
przejazdów rl,1, rl,2,...,rl,sl-1
pomiędzy przystankami --- rl,1
jest czasem przejazdu od przystanku
pl,1 do pl,2, lub z powrotem, tj. od przystanku
pl,2 do pl,1;
rl,2 jest czasem przejazdu od przystanku pl,2 do pl,3, itd.
Wszystkie przystanki linii są różne, tj.\ dla i<>j zachodzi
pl,i<>pl,j.
Na danej linii l pojazdy kursują z określoną częstotliwością
cl, gdzie cl jest liczbą ze zbioru {6, 10, 12, 15, 20, 30, 60}.
Pojazdy linii wyruszają z przystanku pl,1 o każdej okrągłej
godzinie doby, g:0, (0<=g<=23),
a następnie zgodnie z częstotliwością linii, a więc o godzinach
g:cl,g:2cl,... itd.
(g:cl oznacza cl minut po godzinie g).
Ruch pojazdów linii odbywa się jednocześnie w obu kierunkach:
z przystanku pl,1 do pl,sl,
a także z przystanku pl,sl do pl,1.
Godziny odjazdów pojazdów linii z przystanku pl,sl są takie same,
jak z przystanku pl,1.
W tak zdefiniowanej sieci komunikacji publicznej chcemy odbyć podróż z
przystanku początkowego x,
do przystanku końcowego y.
Zakładamy, że podróż
jest możliwa i
nie będzie trwała dłużej
niż 24 godziny.
W trakcie podróży możemy się przesiadać dowolną
liczbę razy z jednej linii komunikacyjnej na inną.
Przyjmujemy, że czas dokonania przesiadki jest równy 0, jednakowoż,
zmieniając linię musimy liczyć się z koniecznością
czekania na pojazd linii, do którego chcemy się przesiąść.
Naszym celem jest odbycie podróży z przystanku początkowego x, do
przystanku końcowego y, w minimalnym czasie.
Przykład
Na poniższym rysunku przedstawiono schemat sieci komunikacyjnej o
6 przystankach i dwóch liniach: 1 i 2.
Pojazdy linii 1 kursują pomiędzy przystankami 1, 3, 4 i 6, a
linii 2 pomiędzy przystankami 2, 4, 3 i 5.
Częstotliwości kursowania pojazdów linii wynoszą, odpowiednio,
c1=15 oraz c2=20.
Czasy przejazdów pomiędzy przystankami umieszczono obok
krawędzi sieci opatrując je indeksami 1 i 2 dla poszczególnych linii.
Załóżmy, że o godzinie 23:30 znajdujemy się na przystanku
początkowym 5 i chcemy odbyć podróż do przystanku końcowego 6.
Wówczas musimy odczekać 10 minut i o godzinie 23:40 wyjeżdżamy
linią 2.
Nasza podróż może mieć dwa warianty.
W pierwszym wariancie, po dojechaniu do przystanku 3 o godzinie 23:51
i odczekaniu 3 minut, przesiadamy się o godzinie 23:54
na linię 1 i dojeżdżamy do przystanku 6 o godzinie 0:16
(następnego dnia).
W drugim wariancie, dojeżdżamy linią 2 do przystanku 4 o
godzinie 0:8, czekamy 13 minut i o godzinie 0:21 wsiadamy do
pojazdu linii 1, osiągając przystanek końcowy 6 o godzinie 0:31.
Tak więc najwcześniej możemy dotrzeć do przystanku 6 o godzinie 0:16.
Zadanie
Napisz program, który:
-
wczyta z pliku tekstowego POD.IN opis sieci oraz linii
komunikacyjnych, numer przystanku początkowego x,
numer przystanku końcowego y,
godzinę początkową gx oraz minuty początkowe mx,
-
wyznaczy minimalny czas podróży od przystanku
początkowego x, do przystanku końcowego y,
-
zapisze do pliku tekstowego POD.OUT najwcześniejszą
możliwą godzinę z minutami dotarcia do przystanku y ---
odpowiednio, gy oraz my.
Wejście
W pierwszym wierszu pliku tekstowego POD.IN zapisanych jest sześć
liczb całkowitych, pooddzielanych pojedynczymi odstępami:
-
liczba przystanków n
(1<=n<=1000),
-
liczba linii komunikacyjnych k
(1<=k<=2000),
-
numer przystanku początkowego x
(1<=x<=n),
-
numer przystanku końcowego y
(1<=y<=n),
-
godzina rozpoczęcia podróży gx
(0<=gx<=23),
-
minuta rozpoczęcia podróży mx
(0<=mx<=59).
Przystanki są ponumerowane od 1 do n,
a linie komunikacyjne od 1 do k.
W kolejnych 3k wierszach opisane są kolejne linie komunikacyjne ---
opis każdej linii zajmuje trzy kolejne wiersze.
-
W pierwszym wierszu opisującym linię komunikacyjną l są
zapisane dwie liczby całkowite, oddzielone pojedynczym odstępem:
sl, równa liczbie przystanków
(2<=sl<=n), oraz
cl, równa częstotliwości kursowania pojazdów
(cl należy do: {6, 10, 12, 15, 20, 30, 60}).
-
W drugim wierszu opisującym linię komunikacyjną l jest
zapisanych sl różnych liczb całkowitych, pooddzielanych
pojedynczymi odstępami: pl,1,pl,2,...,pl,sl
--- numery kolejnych przystanków na tej linii
(1<=pl,i<=n, dla 1<=i<=sl).
-
W trzecim wierszu opisującym linię komunikacyjną l jest
zapisanych sl-1 liczb całkowitych, pooddzielanych
pojedynczymi odstępami: rl,1, rl,2,..., rl,sl-1
--- czasy przejazdów (w minutach) pomiędzy kolejnymi
przystankami na tej linii
(1<=rl,i<=240,
dla 1<=i<=sl-1).
Suma liczb przystanków, na wszystkich liniach razem, nie przekracza 4000
(tzn. s1+s2+...+sk<=4000).
Wyjście
Twój program powinien zapisać w pierwszym i jedynym wierszu
pliku tekstowego POD.OUT dwie liczby całkowite oddzielone
pojedynczym odstępem: godzinę dotarcia do przystanku końcowego
gy (0<=gy<=23) oraz minutę dotarcia do przystanku końcowego
my (0<=my<=59).
Przykład
Dla pliku wejściowego 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
poprawną odpowiedzią jest plik wyjściowy POD.OUT
0 16
|
