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.
Ministerstwo Infrastruktury Bajtocji postanowiło stworzyć program pozwalający szybko obliczać długości tras między dowolnymi miastami. Nie byłoby w tym nic dziwnego, gdyby nie fakt, iż mieszkańcy Bajtocji nie zawsze szukają najkrótszej trasy. Zdarza się, że pragną dowiedzieć się o -tą co do długości najkrótszą trasę. Dopuszczamy zapętlenia tras, tzn. takie trasy, na których miasta powtarzają się.
Jeśli między dwoma miastami istnieją 4 trasy o długościach: 2, 4, 4 i 5, to najkrótsze połączenie ma długość 2, drugie co do długości 4, trzecie 4, a czwarte 5.
Napisz program, który:
W pierwszym wierszu standardowego wejścia zapisane są dwie dodatnie liczby całkowite i oddzielone pojedynczym odstępem, , . Są to odpowiednio liczba miast w Bajtocji oraz liczba dróg łączących miasta. Miasta są ponumerowane od do .
W każdym z kolejnych wierszy znajdują się po trzy liczby całkowite oddzielone pojedynczymi odstępami: , i , , . Każda taka trójka opisuje jedną, jednokierunkową drogę długości umożliwiającą przejechanie z miasta do . Dla każdych dwóch miast istnieje co najwyżej jedna droga umożliwiająca przejazd w danym kierunku.
W kolejnym wierszu znajduje się jedna liczba całkowita , , oznaczająca ilość zapytań. W kolejnych wierszach są zapisane zapytania, po jednym w wierszu. Każde zapytanie to trzy liczby całkowite oddzielone pojedynczymi odstępami: , i , . Zapytanie takie dotyczy długości -tej najkrótszej trasy z miasta do miasta .
Twój program powinien wypisywać odpowiedzi na wczytane zapytania na standardowe wyjście, po jednej odpowiedzi w wierszu. W -tym wierszu powinna zostać wypisana odpowiedź na -te zapytanie - jedna liczba całkowita równa szukanej długości trasy lub -1, gdy taka trasa nie istnieje.
Dla danych wejściowych:
5 5 1 2 3 2 3 2 3 2 1 1 3 10 1 4 1 8 1 3 1 1 3 2 1 3 3 1 4 2 2 5 1 2 2 1 2 2 2 1 1 2
poprawną odpowiedzią jest:
5 8 10 -1 -1 3 6 -1
Autor zadania: Krzysztof Sikora.