Atrakcje turystyczne

Limit pamięci: 64 MB

Bajtazar jedzie z Bitowic do Bajtogrodu. Po drodze chce odwiedzić kilka wybranych miejscowości, w których znajdują się interesujące zabytki, dobre restauracje, czy inne atrakcje turystyczne. Kolejność odwiedzania wybranych miejscowości nie jest całkowicie obojętna. Na przykład, Bajtazar wolałby nie wspinać się na wieżę zamku Bitborku po sutym obiedzie zjedzonym w Cyfronicach, a do Zipowic (na słynną kawę Compresso) chciałby wpaść raczej po obiedzie, a nie przed. Jednak kolejność odwiedzania wybranych miejscowości nie jest całkowicie ustalona i do pewnego stopnia elastyczna. Ze względu na obłędne ceny benzyny, Bajtazar chce tak zaplanować trasę przejazdu, żeby była jak najkrótsza. Pomóż mu wyznaczyć długość najkrótszej trasy spełniającej jego wymagania.

Sieć drogowa składa się z miejscowości i łączących je dróg. Miejscowości są ponumerowane od 1 do , a drogi od 1 do . Każda droga łączy dwie różne miejscowości i jest dwukierunkowa. Drogi spotykają się tylko w miejscowościach (w których mają końce) i nie przecinają się poza nimi. Drogi mogą prowadzić przez estakady i tunele. Każda droga ma określoną długość. Parę miejscowości może łączyć co najwyżej jedna bezpośrednia droga.

Oznaczmy przez liczbę wybranych miejscowości, które chce odwiedzić Bajtazar. Numeracja miast jest taka, że Bitowice mają numer 1, Bajtogród numer , a miejscowości, które chce odwiedzić Bajtazar mają numery .

Na rysunku przedstawiono przykładową sieć dróg. Powiedzmy, że Bajtazar chce odwiedzić miejscowości 2, 3, 4 i 5, przy czym miejscowość 2 chce odwiedzić przed miejscowością 3, a miejscowości 4 i 5 po miejscowości 3. Wówczas najkrótsza trasa biegnie przez miejscowości 1, 2, 4, 3, 4, 5, 8 i ma ona długość 19.

Zauważmy, że miejscowość 4 pojawia się na tej trasie przed i po miejscowości 3. Jednak przed odwiedzeniem miejscowości 3 Bajtazar nie zatrzyma się w niej, gdyż takie przyjął ograniczenia. Nie oznacza to jednak, że w ogóle nie może wcześniej przejeżdżać przez tę miejscowość.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis sieci drogowej, listę wybranych miejscowości, które chce odwiedzić Bajtazar oraz ograniczenia, co do kolejności, w jakiej chce je odwiedzić,
• wyznaczy długość najkrótszej trasy, przechodzącej przez wszystkie wybrane przez Bajtazara miejscowości w odpowiedniej kolejności,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite , i pooddzielane pojedynczymi odstępami, , , ; ponadto jest spełniona nierówność .

Kolejne wierszy zawiera opisy dróg, po jednej w wierszu. Wiersz -szy zawiera trzy liczby całkowite , i , pooddzielane pojedynczymi odstępami, , . Liczby te oznaczają drogę łączącą miejscowości i , długości . Możesz założyć, że dla każdych danych testowych można z Bitowic dojechać do Bajtogrodu oraz do wszystkich miejscowości, które Bajtazar chce odwiedzić.

W -szym wierszu znajduje się jedna liczba całkowita , . Jest to liczba ograniczeń dotyczących kolejności odwiedzania wybranych przez Bajtazara miast. Ograniczenia te są podane w kolejnych wierszach, po jednym w wierszu. Wiersz -szy zawiera dwie liczby całkowite i oddzielone pojedynczym odstępem, , , . Para liczb i oznacza, że Bajtazar chce odwiedzić miejscowość przed odwiedzeniem miejscowości . Nie oznacza to, że nie może przejechać przez przed odwiedzeniem , ani że nie może przejechać przez po odwiedzeniu , jednak nie będzie się on wtedy zatrzymywał ani zwiedzał żadnych atrakcji turystycznych. Możesz założyć, że dla każdych danych testowych istnieje przynajmniej jedna kolejność zwiedzania wybranych miejscowości spełniająca wszystkie ograniczenia.

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia należy wypisać jedną liczbę całkowitą, będącą długością najkrótszej trasy z Bitowic do Bajtogrodu, przechodzącej przez wszystkie wybrane przez Bajtazara miejscowości w odpowiedniej kolejności.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

19

Rysunek i wyjaśnienie do przykładu znajdują się w treści zadania.

Autor zadania: Zbigniew Czech.