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.
Drogi w Dalekim Kraju są w bardzo złym stanie, ale pozwalają na dotarcie z każdego miasta do dowolnego innego (choć może to wymagać odwiedzenia wielu miast). Żeby temu zaradzić rząd Dalekiego Kraju postanowił wybudować autostrady. Z braku pieniedzy zdecydowano się na budowę najmniejszej możliwej liczby autostrad, które umożliwią przejazd pomiędzy dwoma dowolnymi miastami. Autostrady mają być zbudowane w miejsce istniejących (wybranych) dróg. Znany jest koszt przebudowy każdej drogi. Okazało się, że koszty przebudowy różnych dróg są różne. Autostrady mają zbudować prywatne przedsiębiorstwa za pieniądze publiczne. Rząd wie, że opinię społeczną nie tyle interesuje łączny koszt wybudowania wszystkich autostrad, ale to ile zarobią poszczególne przedsiebiorstwa. Dlatego zdecydowano się na wybudowanie takiej sieci autostrad, żeby koszt najdroższej z nich był jak najmniejszy. Jaki jest koszt budowy najdroższej autostrady przy takim założeniu? Wszystkie drogi i autostrady są dwukierunkowe.
Napisz program, który:
W pierwszym wierszu podane są dwie liczby całkowite (), oddzielone pojedynczym odstępem. Liczba jest liczbą miast w Dalekim Kraju. Miasta są ponumerowane od 1 do . Liczba jest liczbą dróg. Każda droga łączy bezpośrednio dwa miasta. Każdy z następnych wierszy zawiera trzy liczby całkowite opisujące jedną drogę wraz z kosztem jej przebudowy. Liczby oddzielone są pojedynczymi znakami odstępu. Dwie pierwsze liczby są numerami miast, które ta droga łączy, natomiast trzecia liczba jest kosztem przebudowy drogi na autostradę. Koszt pojedyczej przebudowy jest dodatnią liczbą całkowitą nie większą niż .
Pierwszy i jedyny wiersz powinien zawierać koszt budowy najdroższej autostrady przy spełnieniu warunków zadania.
Dla danych wejściowych:
10 19 10 7 9 7 10 100 10 7 77 5 4 3 3 9 4 3 5 6 1 4 1 10 1 7 8 9 8 2 9 3 10 5 5 8 10 6 3 1 9 5 2 7 2 3 2 7 4 8 10 4 1 5 6 1 10 6 2
poprawną odpowiedzią jest:
8<Wyślij rozwiązanie> [0/100]