In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
To zadanie pochodzi z Kółka Informatycznego w Staszicu.
autor: Piotr Cerobski
Bajtazar jest miłośnikiem wycieczek górskich. Niestety cierpi na astmę i gdy wejdzie na zbyt dużą wysokość to zaczyna się dusić. Z tego powodu musi bardzo dokładnie planować swoje wyprawy. Jednak nie jest to proste. Bajtazar posiada bardzo dokładne mapy gór z dziesiątkami tysięcy szlaków, każdy szlak zaczyna się na pewnej wysokości i na jakiejś kończy. Nasz bohater ustalił miejsce skąd wyrusza i dokąd się kieruje jednak przytłoczony ilością informacji za bardzo sobie nie radzi z ułożeniem optymalnej trasy.
Pomóż Bajtazarowi w ułożeniu wycieczki. Napisz program który wczyta opis gór (punkty na różnych wysokościach połączone szlakami) i powie na jaką minimalną wysokość musi wejść Bajtazar aby dojść do wyznaczonego miejsca.
W pierwszym wierszu znajdują się liczby N i M (1<=N<=100000; 1<=M<=300000), które oznaczają odpowiednio ilość punktów na mapie i ilość szlaków. W następnych N wierszach znajdują się wysokości na których leżą punkty. Wysokości to liczby całkowite z przedziału 1..1000000. W K+1 wierszu znajduje się wysokość K-tego wierzchołka. W każdym z następnych M wierszy znajduje się opis szlaku. Składa się on z dwóch liczb A B, które mówią, iż szlak ten prowadzi od punktu A do punktu B. Po szlakach można chodzić w obie strony i można założyć że wysokość, na której leży szlak mieści się między wysokością A i B.
Twój program powinien wypisać minimalną wysokość, na którą musi wejść Bajtazar, aby przejść po szlakach z wierzchołka 1 do wierzchołka n. Możesz założyć, że jakaś droga zawsze istnieje.
Dla danych wejściowych:
9 11 3 10 9 6 8 3 2 4 1 1 2 1 3 7 1 4 1 4 6 5 3 6 7 7 8 8 9 6 9 5 9
program powinien wypisać liczbę:
3
(jest to droga 1-7-6-9)