Problem
Znalezienie trasy o najmniejszym koszcie pomiędzy dwoma miastami na podstawie danych z „mapy”.
Wejście
Na wejściu pojawiają się dane definiujące „mapę” drogową.
W pierwszej linii liczba naturalna 0 < m <= 100 = liczba połączeń między miastami.
W kolejnych 3*m liniach dane definiujące kolejne połączenia w następującym formacie:
1. linia - nazwa miasta A (początkowego),
2. linia - nazwa miasta B (końcowego),
3. linia - koszt przejazdu z A do B (nieujemna liczba całkowita).
Po definicji połączeń w dwóch ostatnich liniach
nazwy dwóch miast S i V (występujących w liście połączeń).
Uwaga Mapa jest definiowana jako graf skierowany, tj. istnienie połączenia z A do B nie implikuje automatycznie istnienia połączenia z B do A!
Wyjście - dwie możliwości
(1) Gdy istnieje droga z S do V, na wyjściu powinna się pojawić droga z S do V o najmniejszym koszcie w formie serii nazw miast od S do V (w jednej linii, oddzielone stringiem ' -> ' tj. spacja minus > spacja).
W drugiej linii koszt tej trasy.
(2) W przeciwnym wypadku napis 'nie ma drogi'.
Przykładowe wejście I
7
Torun
Bydgoszcz
60
Torun
Gdansk
100
Bydgoszcz
Szczecin
200
Gdansk
Szczecin
100
Szczecin
Kopenhaga
500
Warszawa
Torun
200
Warszawa
Gdansk
350
Warszawa
Kopenhaga
Wynik I
Warszawa -> Torun -> Gdansk -> Szczecin -> Kopenhaga
900
Przykładowe wejście II
1
Kobylaki Czarzaste
Nowe Laski
111
Nowe Laski
Kobylaki Czarzaste
Wynik II
nie ma drogi
