In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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ść.
Napisz program, który:
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.
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.
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.