W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Bajtazar jest królem Bajtocji, wyspy na Oceanie Szczęśliwości. Bajtocja ma kształt figury wypukłej, a wszystkie miasta w niej są położone nad brzegiem oceanu. Jedno z tych miast to Bajtogród, stolica Bajtocji. Każde dwa miasta są połączone drogą biegnącą przez wyspę po prostej łączącej oba miasta. Drogi łączące różne pary miast przecinają się, tworząc skrzyżowania.
Bitocy, konkurent Bajtazara do tronu, zaplanował nikczemny spisek. W trakcie podróży Bajtazara ze stolicy do sąsiedniego miasta opanował Bajtogród. Bajtazar musi jak najszybciej powrócić do Bajtogrodu, by odzyskać władzę. Niestety niektóre z dróg są patrolowane przez zbrojne bojówki Bitocego. Bajtazar nie może poruszać się takimi drogami, choć może przekraczać je na skrzyżowaniach. Na trasie może on skręcać wyłącznie na skrzyżowaniach.
Bajtazar wie, które drogi są patrolowane przez bojówki Bitocego. Poprosił Cię o wyznaczenie najkrótszej bezpiecznej trasy z miasta, w którym się aktualnie znajduje, do Bajtogrodu.
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite i , oddzielone pojedynczym odstępem (, ), oznaczające odpowiednio: liczbę miast oraz liczbę dróg patrolowanych przez bojówki Bitocego. Ponumerujmy miasta od 1 do , zaczynając od Bajtogrodu i idąc wzdłuż brzegu zgodnie z ruchem wskazówek zegara. Bajtazar znajduje się w mieście nr . W każdym z kolejnych wierszy znajduje się para liczb i (), oddzielonych pojedynczym odstępem, oznaczających współrzędne miasta nr na wyspie.
W każdym z kolejnych wierszy znajduje się para liczb i (). Para taka oznacza, że droga łącząca miasta i jest patrolowana przez bojówki Bitocego. Pary liczb opisujące patrolowane drogi nie powtarzają się. Możesz założyć, że dla każdych danych testowych Bajtazar może dostać się do Bajtogrodu.
Twój program powinien wypisać na standardowe wyjście jedną liczbę zmiennopozycyjną: długość najkrótszej bezpiecznej trasy prowadzącej z miasta do Bajtogrodu. Wynik Twojego programu może różnić się od poprawnego o co najwyżej .
Dla danych wejściowych:
6 9 -12 -10 -11 6 -4 12 6 14 16 6 18 -2 3 4 1 5 2 6 2 3 4 5 3 5 1 3 3 6 1 6
poprawną odpowiedzią jest:
42.0000000000
Trasa, którą powinien podążać Bajtazar, wychodzi z miasta 6 w kierunku miasta 4, następnie biegnie drogą łączącą miasta 2 i 5, a na koniec drogą łączącą Bajtogród z miastem 4.
Autor zadania: Jakub Onufry Wojtaszczyk.