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.
Bajdonald postanowił uruchomić w Bajtocji sieć restauracji. Jego pragnieniem jest, żeby każdy mieszkaniec mógł choćby raz w tygodniu wybrać się do jednej z nich.
Wstępnie zaplanował już, w których miastach postawi swoje restauracje. Obawia się jednak, czy z każdego miasta będzie można w rozsądnym czasie dojechać do jakiejkolwiek z nich. Chciałby więc dowiedzieć się, jaką największą odległość trzeba pokonać, żeby dostać się do najbliższej restauracji. Jeśli ta odległość okaże się zbyt duża, będzie musiał zmienić swoje plany.
Miasta w Bajtocji są połączone siecią dwukierunkowych autostrad. Wiadomo, że z każdego miasta można dojechać do każdego innego, choć nie zawsze bezpośrednio. Mieszkańcy Bajtocji żyją tylko w miastach.
Napisz program, który:
W pierwszym wierszu wejścia znajdują się trzy liczby całkowite ,
i
,
,
,
oddzielone pojedynczymi odstępami, określające odpowiednio - liczbę miast w Bajtocji, liczbę planowanych restauracji oraz liczbę autostrad.
Miasta są ponumerowane od
do
.
W każdym z kolejnych wierszy znajduje się jedna liczba - numer miasta, w którym ma być zbudowana restauracja.
W każdym z następnych
wierszy znajdują się trzy liczby całkowite
,
i
,
oddzielone pojedynczymi odstępami.
Liczby te opisują jedną autostradę - autostrada łączy miasta
i
(
), a jej długość wynosi
km,
.
W jedynym wierszu standardowego wyjścia powinna zostać zapisana jedna liczba całkowita, równa maksymalnej odlegości (w kilometrach) pomiędzy pewnym miastem, a najbliżej położoną restauracją.
Dla danych wejściowych:
3 1 3 1 1 2 10 1 3 15 3 2 20
poprawną odpowiedzią jest:
15