Polish version    English version  
  Historia OI -> IX OI 2001/2002 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
Przepisy
Dla zawodnikow
Przydatne zasoby
Statystyki
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
IX Olimpiada Informatyczna 2001/2002

Zadanie: kur
Autor: Marcin Sawicki
Kurort narciarski

Zawody II stopnia, dzień drugi  
Plik źródłowy: kur.??? (np. pas, c, cpp)
Plik wejściowy: kur.in
Plik wyjściowy: kur.out

W Bajtogórach znajduje się kurort narciarski Bajtyrk słynący z narciarskich tras biegowych. Są one bardzo malownicze, gdyż część z nich jest położona wysoko w górach lub w trudno dostępnych miejscach. Użytkownicy tras często korzystają z wyciągów ułatwiających dotarcie do niektórych z nich. Każdy wyciąg i każda trasa zaczyna się i kończy na określonej polanie. Trasy narciarskie nie mogą się przecinać, ale mogą przebiegać naturalnymi skalnymi tunelami i estakadami.

Trasy narciarskie mogą być jednokierunkowe lub dwukierunkowe. Podobnie, niektóre wyciągi (kolejki linowe) mogą być jedno lub dwukierunkowe.

Za korzystanie z wyciągów płaci się kartą magnetyczną. Karty kupuje się w kasach. Każda karta zawiera określoną liczbę punktów. Skorzystanie z każdego z wyciągów wiąże się z utratą pewnej liczby punktów zależnej od wyciągu. Niestety kasy nie zwracają pieniędzy za niewykorzystane punkty.

Bajtoni jest dziś na nartach ostatni dzień. Została mu jedna karta z pewną liczbą punktów, które chciałby wykorzystać do maksimum. Możesz założyc, że ta liczba punktów wystarczy na powrót do Bajtyrku.

Zadanie

Napisz program, który:

  • wczyta z pliku tekstowego kur.in opis sieci tras i wyciągów oraz informacje o położeniu Bajtoniego i liczbie punktów na jego karcie,
  • obliczy, z jaką najmniejszą liczbą punktów na karcie Bajtoni może dziś wrócić na dół, do Bajtyrku,
  • zapisze wynik w pliku tekstowym kur.out.

Wejście

W pierwszym wierszu pliku tekstowego kur.in zapisane są dwie dodatnie liczby całkowite n i n', 1 <= n' < n <= 1000, oddzielone pojedynczym odstępem, oznaczające odpowiednio liczbę wszystkich polan oraz liczbę tych polan, które znajdują się na dole w samym Bajtyrku (są to polany o numerach od 1 do n' włącznie).

W drugim wierszu zapisana jest jedna dodatnia liczba całkowita k, 1 <= k <= 5000, równa łącznej liczbie wszystkich tras narciarskich. Każdy z kolejnych k wierszy zawiera po dwie różne dodatnie liczby całkowite, pooddzielane pojedynczymi odstępami, 1 <= p1 <> p2 < n. Liczby te oznaczają numer początkowej i końcowej polany danej trasy narciarskiej. Trasy dwukierunkowe są tu liczone dwukrotnie i reprezentowane w pliku wejściowym przez dwa (niekoniecznie kolejne) wiersze (postaci "p1 p2" i "p2 p1").

W k+3-cim wierszu zapisana jest jedna dodatnia liczba całkowita m, 1 <= m <= 300, równa liczbie wszystkich wyciągów. W kolejnych m wierszach opisane są wyciągi. W każdym z tych wierszy zapisane są trzy dodatnie liczby całkowite q1, q2 i r, pooddzielane pojedynczymi odstępami. Liczby q1 i q2 oznaczają odpowiednio numer polany, na której wyciąg się zaczyna i numer polany, na której się kończy, 1 <= q1 <> q2 <= n. Liczba r jest równa liczbie punktów, które trzeba zapłacić za przejazd wyciągiem, 1 <= r <= 1000. Wyciągi dwukierunkowe (kolejki linowe) są tu liczone dwukrotnie i reprezentowane w pliku wejściowym przez dwa (niekoniecznie kolejne) wiersze (postaci "q1 q2 r1" i "q2 q1 r2"). Ceny przejazdu wyciągiem w jedną i w drugą stronę mogą być różne.

W ostatnim wierszu zapisane są dwie dodatnie liczby całkowite b i s, oddzielone pojedynczym odstępem, 1 <= b <= n, 1 <= s <= 2000. Pierwsza z nich oznacza numer polany, na której znajduje się Bajtoni a druga jest równa liczbie punktów na jego ostatniej karcie magnetycznej.

Wyjście

Twój program powinien zapisać w pierwszym (i jedynym) wierszu pliku tekstowego kur.out jedną liczbę całkowitą, równą najmniejszej możliwej liczbie punktów, z jaką Bajtoni może wrócić do Bajtyrku.

Przykład

Dla pliku wejściowego kur.in:

5 2
6
3 2
3 5
1 5
3 4
1 2
4 3
4
3 1 1
4 3 5
5 2 2
3 4 5
4 9
poprawną odpowiedzią jest plik wyjściowy kur.out:
1



Wersja do druku