Polish version    English version  
  O olimpiadzie -> Zadania


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
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



Wersja do druku