In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Jacek chce oblecieć świat dookoła. Niestety nie ma zbyt wielu pieniędzy, wobec czego chce to zrobić jak najtaniej. Jacek zorientował się, że stosunkowo tanie są loty Bajtolinii Lotniczych, dlatego sprawdził wszystkie połączenia w ich ofercie. Siedzi teraz nad mapą i kombinuje. Pomóż mu!
Dane Jacka to lista miast oraz lista połączeń między tymi miastami. Dla każdego z miast Jacek zna jego długość geograficzną. Każdy z lotów łączy dwa miasta i umożliwia podróż w obydwóch kierunkach - jeśli z miasta do miasta możemy dolecieć za bajtalarów, to podróż z miasta do miasta również jest możliwa i kosztuje bajtalarów.
Dla każdego połączenia wiemy, czy samoloty wykonujące to połączenie lecą na zachód, czy też na wschód (zakładamy, że żadne dwa miasta nie mają tej samej długości geograficznej). Każdy samolot leci cały czas wprost do celu, a trasa żadnego lotu nie prowadzi nad biegunem i nie okrąża Ziemi w pełni (tj. samolot przebywa mniej niż długości geograficznej).
Powstał jeszcze jeden problem. Co to znaczy "oblecieć świat dookoła"? Jacek ustalił, że chce, aby podczas całej podróży łączna liczba stopni długości geograficznej przebytych na wschód była różna od liczby stopni przebytych w kierunku zachodnim. Jacek planuje rozpocząć i zakończyć podróż w swoim rodzinnym mieście.
Rozważmy następujące przykłady (zakładamy w nich, że wszystkie loty są w rozsądnym kierunku, tj. w tym, w którym przelatujemy mniej niż 180 stopni):
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i () oznaczające odpowiednio liczbę miast na mapie Jacka oraz liczbę lotów dostępnych w Bajtoliniach Lotniczych. Miasta są ponumerowane liczbami od do . Jacek rozpoczyna podróż w mieście numer . W drugim wierszu znajdują się współrzędne kolejnych miast podane jako ciąg liczb całkowitych (). Liczba oznacza, ile sekund geograficznych na wschód od południka zerowego leży miasto numer ( sekunda to stopnia). Żadne dwa miasta nie mają tej samej długości geograficznej.
Każdy z kolejnych wierszy opisuje jeden lot. W -tym z tych wierszy znajdują się cztery liczby całkowite (, , , ). Oznaczają one, że Bajtolinie oferują przeloty pomiędzy miastami numer oraz w cenie bajtalarów i trasa lotu z miasta do miasta prowadzi na wschód (gdy ) lub na zachód (gdy ). Trasa lotu powrotnego prowadzi w przeciwnym kierunku.
Twój program powinien wypisać na wyjście koszt (w bajtalarach) najtańszej podróży dookoła świata, która rozpoczyna się i kończy się w mieście numer . Jeśli takiej podróży nie ma, program powinien wypisać .
Dla danych wejściowych:
5 7 75630 135420 502890 1029600 870750 4 3 1 1 3 2 4 -1 3 5 7 1 1 5 15 1 1 4 10 -1 1 2 2 1 5 4 3 1
poprawną odpowiedzią jest:
23
Autor zadania: Jakub Wojtaszczyk.