Zadanie Wyprawa (jou)

Wyprawa

Limit pamięci: 32 MB

W Bajtocji jest miast (ponumerowanych liczbami od do ). Miasta są połączone dwukierunkowymi drogami. Ponieważ król Bajtocji nie jest zbyt skory do inwestycji w rozbudowę dróg, jest ich zaledwie . Można jednak przy ich pomocy dotrzeć z dowolnego miasta do dowolnego innego miasta.

Pewnego dnia, podróżnik Bajtazar zawitał do miasta o numerze . Zamierza on odwiedzić jeszcze miasta , , ..., (niekoniecznie w tej kolejności) - liczby są parami różne i wszystkie są różne od . Bajtazarowi powoli kończą się fundusze przeznaczone na podróż, dlatego chciałby objechać wszystkie zaplanowane miasta za pomocą możliwie najkrótszej trasy (zaczynającej się w mieście ). Przez trasę rozumiemy ciąg jednej lub więcej dróg, w którym początek następnej drogi jest końcem poprzedniej. Pomóż Bajtazarowi wyznaczyć długość najkrótszej trasy odwiedzającej wybrane przez niego miasta.

Zadanie

Napisz program, który:

wczyta ze standardowego wejścia:
- opis bajtockiej sieci dróg,
- numer miasta, w którym znajduje się Bajtazar,
- listę miast, które Bajtazar chciałby odwiedzić
wyznaczy minimalną długość trasy Bajtazara
wypisze wynik na standardowe wyjście

Wejście

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite i oddzielone pojedynczym odstępem (, ), gdzie jest liczbą miast w Bajtocji, a - numerem miasta, w którym znajduje się Bajtazar.

Każdy z kolejnych wierszy opisuje jedną z dróg Bajtocji. Wiersz -szy (dla ) zawiera trzy liczby całkowite , i oddzielone pojedynczymi odstępami (, ), i są miastami połączonymi drogą, a jest długością drogi. Wiersz -szy zawiera pojedynczą liczbę całkowitą - liczbę miast, które Bajtazar chciałby odwiedzić (). Kolejny wiersz zawiera różnych liczb całkowitych oddzielonych pojedynczymi odstępami - są to numery miast wybranych przez Bajtazara (, ).