In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
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.
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]