W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Biednemu zawsze wiatr w oczy. Niedźwiedź (główny bohater zadania Niedźwiedź) bardzo ucieszył się, że nadeszła wczesna zima i już nie będzie musiał przemykać po lesie, cały czas brodząc po kolana w błocie i bacząc na czyhające na niego owady. Niestety, zima postanowiła uprzykrzyć życie Niedźwiedzia i śniegu nasypało tyle, że nasz bohater ledwo może się przemieszczać po lesie.
Niedźwiedź postanowił nie poddawać się i odśnieżyć las, a przynajmniej ścieżki prowadzące do trzech polan, koło których zazwyczaj łapie on ryby na kolację. Las składa się z polan połączonych (dwukierunkowymi) ścieżkami. Polany są ponumerowane liczbami od do . Wygląda na to, że niektóre ścieżki mogą biec tunelami lub estakadami, co nieco zdziwiło Niedźwiedzia, ale ma on teraz poważniejsze problemy na głowie. Dla każdej ścieżki Niedźwiedź wie, ile czasu będzie potrzebować na jej odśnieżenie.
Ile czasu będzie on musiał spędzić na odśnieżenie tylu ścieżek, by mógł poruszać się między swoją norą (położoną obok polany numer ), a polanami, koło których łapie ryby, chodząc jedynie po odśnieżonych ścieżkach?
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i (, ). Oznaczają one kolejno liczbę polan w lesie oraz liczbę łączących je ścieżek. Drugi wiersz zawiera trzy różne od siebie liczby całkowite () – są to numery polan, przy których Niedźwiedź łapie ryby. Każdy z kolejnych wierszy opisuje jedną ścieżkę. W -tym z tych wierszy znajdują się trzy liczby całkowite (, , ). Oznaczają one, że polany o numerach i są połączone dwukierunkową ścieżką, której odśnieżenie zajmie sekund. Każda para polan może być połączona co najwyżej jedną ścieżką. Pomiędzy każdą parą polan ze zbioru można przejść, idąc po ścieżkach.
Na wyjściu należy wypisać minimalną liczbę sekund potrzebną do odśnieżenia ścieżek, które umożliwią poruszanie się między polanami numer , , i .
Dla danych wejściowych:
7 8 3 6 7 1 2 2 1 4 3 2 3 4 3 5 3 3 7 5 4 5 3 4 6 5 5 7 4
poprawną odpowiedzią jest:
18
W testach wartych co najmniej punktów zachodzi oraz .
Autor zadania: Marcin Mucha.