Algorytm Dijkstry

25.11.2009 - Krzysztof Nowicki
TrudnośćTrudność

Zadania

 

Dostawca

 

Limit  czasowy: 4s; Limit pamięciowy: 64 MB;

Dostawca Kazimierz zajmuje się dostarczaniem, nie jest jednak bezpośrednim dostarczycielem, ale zajmuje się koordynowaniem. Do jego zadań należy znajdowanie najkrótszych dróg dla kierowców. Pan Kazimierz dysponuje mapą oraz opisem transportów (w którym mieście jest kierowca i do którego miasta ma coś zawieźć). Pomóż pamu Kazimierzowi znaleźć najkrótsze drogi dla dostawców mając opis mapy oraz transportów.

Wejście:

W pierwszej linii podane są dwie liczby $ v $<1001 i $ e $ oznaczające ilość miast oraz ilość połączeń między nimi. W kolejnych $ e $ liniach znajdują się trójki liczb $ a $,$ b $, oraz $ c $ oznaczające, że pomiędzy miastami $ a $ i $ b $ jest droga o nieujemnej długości $ c $<1001.

W kolejnym wierszu znajduje się $ t $<100 liczba transportów dla których pan Kazimierz chce znać najkrótszą drogę. W kolejnych $ t $ wierszach znajdują się pary liczb $ g $,$ h $, które ozanczają, że transport ma dotrzeć z miasta $ g $ do miasta $ h $.

Wyjście:

Skłąda się z $ t $ linii, w $ i $-tej długość najkrótszej drogi pomiędzy miastami z $ i $-tego transportu lub "INF" jeśli droga taka w ogóle nie istnieje. 

Przykład:

Dla wejścia:

8 15
1 2 5
1 3 4
2 3 2
2 3 5
2 6 5
3 5 3
3 4 4
3 6 6
4 6 5
4 7 5
4 8 4
5 6 4
5 7 7
6 7 5
7 8 4
2
1 7
2 2

Poprawne wyjście to:

13
0

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Możliwości

 

Limit czasowy: 4s; Limit pamięciowy: 64MB;

Nadworny geograf króla Mieczysława dostał bardzo nietypowe zadanie. Mianowicie król wymyślił sobie, że chce wiedzieć, jaka jest najkrótsza długość drogi ze stolicy do pewnego miasta. To jednak nie wszystko, co król chciałby wiedzieć od swojego geografa, potrzebna mu jest równiez ilość najkrótszych dróg ze stolicy do owego miasta.modulo pewną liczbę  dodatnią $ m $<1001. Aby geograf nie czuł się niepotrzebny król kazał mu również podać jedną z najkrótszych dróg ze stolicy do owego miasta. Na dodatek nie byle jaką, tylko taką, która jest odpowiednia, mianowicie król wjeżdżając do miasta chce wjeżdżać do niego z sąsiedniego miasta o najmniejszym możliwym numerze. Priorytetem jednak pozostaje to, aby droga była możliwie najkrótsza. Jako, że geograf jest tylko geografem, ma marne szanse aby wywiązać się z zadania samodzielnie. Pomóż ocalić mu głowę i napisz dla niego program, który dla podanego opisu mapy obliczy długość najkrótszej ścieżki do pewnego miasta, ilość najkrótszych ścieżek modulo $ m $ oraz poda odpowiednią ścieżkę.

Wejście:

W pierwszej linii podane są dwie liczby $ v $<1001 i $ e $ oznaczające ilość miast oraz ilość połączeń między nimi. W kolejnych $ e $ liniach znajdują się trójki liczb $ a $,$ b $, oraz $ c $ oznaczające, że pomiędzy miastami $ a $ i $ b $ jest droga o dodatniej długości $ c $<1001.

W kolejnym wierszu znajduje się numer miasta $ x $  dla którego mamy obliczyć odległość ze stolicy (stolica ma numer 1) oraz liczba $ m $.

Wyjście:

Jeśli droga nie istnieje poprawnym wyjściem jest "INF". w przeciwnym wypadku w pierwszej linii powinna się znajdować długość najkrótszej drogi ze stolicy do miasta $ x $. W drugiej ilość ścieżek ze stolicy do miasta $ x $. W trzeciej i ostatniej linii powinien sie znaleźć ciąg numerów miast należących do odpowiedniej ścieżki (w kolejności odwiedzania ich na ścieżce).

 

Przykład:

Dla wejścia:

8 15
1 2 5
1 3 4
2 3 2
2 3 5
2 6 5
3 5 3
3 4 4
3 6 6
4 6 5
4 7 5
4 8 4
5 6 4
5 7 7
6 7 5
7 8 4
6 1000

Poprawne wyjście to:

10
2
1 2 6




Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
3.3
Twoja ocena: Brak Ocena: 3.3 (10 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com