Polish version    English version  
  Historia OI -> X OI 2002/2003


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
Przepisy
Dla zawodnikow
Przydatne zasoby
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
X Olimpiada Informatyczna 2002/2003

Zadanie: pol
Autor: Krzysztof Sikora
Połączenia

Zawody II stopnia, dzień drugi  
Plik źródłowy: pol.xxx (xxx=pas,c,cpp)

Alternatywne formaty: PostScript | PDF

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 k-tą co do długości najkrótszą trasę. Dopuszczamy zapętlenia tras, tzn. takie trasy, na których miasta powtarzają się.

Przykład

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.

Zadanie

Napisz program, który:

  • wczyta ze standardowego wejścia opis sieci dróg Bajtocji oraz zapytania dotyczące długości tras przejazdu,
  • obliczy i wypisze na standardowe wyjście odpowiedzi do wczytanych zapytań.

Wejście

W pierwszym wierszu standardowego wejścia zapisane są dwie dodatnie liczby całkowite n i m oddzielone pojedynczym odstępem, 1 <= n <= 100, 0 <= m <= n2-n. Są to odpowiednio liczba miast w Bajtocji oraz liczba dróg łączących miasta. Miasta są ponumerowane od 1 do n.

W każdym z kolejnych m wierszy znajdują się po trzy liczby całkowite oddzielone pojedynczymi odstępami: a, b i d, a <> b, 1 <= d <= 500. Każda taka trójka opisuje jedną, jednokierunkową drogę długości d umożliwiającą przejechanie z miasta a do b. 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 q, 1 <= q <= 10000, oznaczająca ilość zapytań. W kolejnych q wierszach są zapisane zapytania, po jednym w wierszu. Każde zapytanie to trzy liczby całkowite oddzielone pojedynczymi odstępami: c, d i k, 1 <= k <= 100. Zapytanie takie dotyczy długości k-tej najkrótszej trasy z miasta c do miasta d.

Wyjście

Twój program powinien wypisywać odpowiedzi na wczytane zapytania na standardowe wyjście, po jednej odpowiedzi w wierszu. W i-tym wierszu powinna zostać wypisana odpowiedź na i-te zapytanie - jedna liczba całkowita równa szukanej długości trasy lub -1, gdy taka trasa nie istnieje.

Przykład

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

poprawnym wynikiem jest:

5
8
10
-1
-1
3
6
-1



Wersja do druku