Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
MWP2_2A - Euro 4024 |
Pamiętasz Marka z Politechniki Marsjańskiej? Nie przejmuj się, on Ciebie też nie. Od czasu kiedy częściowo naprawił swój zegarek i przestał się spóźniać jego życie stało się zdecydowanie przyjemniejsze. Nasz znajomy skończył studia i nawet dostał dobrze płatną pracę przy organizacji Euro 4024.
Nazwa to pozostałość po zawodach rozgrywanych dawno temu. Niestety nikt nie wie o co właściwie w nich chodziło. Obecnie Euro to ogromna impreza przyciągająca masę ludzi. Przez dobę ponad 100 zawodników rywalizuje grając w wojnę. Emocje sięgają zenitu ;-) Impreza ta zazwyczaj odbywa się na kilku planetach, dlatego też kibice muszą mieć zapewniony odpowiedni transport. Niestety statki kosmiczne, które będą przewozić kibiców na Euro 4024 są w opłakanym stanie. Na dodatek są to starsze, potwornie wolne modele, lot z jednaj planety na drugą trwa czasami nawet kilka minut. Wszystko to powoduje, że kibice nie dolatują na czas, a kolejki oczekujących na wylot są ogromne. Nie pomaga nawet fakt, że pomiędzy niektórymi parami planet uruchomiono kilka linii.
Organizatorzy mają tego dość, postanowili zmodernizować część linii przed rozpoczęciem imprezy, a resztę po prostu zamknąć. Chcą oni jednak aby koszt inwestycji był jak najmniejszy i aby nadal był możliwy przelot pomiędzy każdą parą planet (może być z przesiadkami). Po tych ustaleniach zapuścili funkcję rand()
no i wypadło, że to Marek obliczy koszt inwestycji. To ile to będzie?
Wejście
W pierwszej linii wejścia znajdują się dwie liczby całkowite p oraz l (1 ≤ p ≤ 700, 1 ≤ l ≤ 500000) określające odpowiednio ilość planet, na których rozgrywane będzie Euro 4024 i ilość obecnie działających linii komunikacji międzyplanetarnej. W kolejnych l wierszach znajdują się opisy tych linii.
Opis każdej linii zawarty jest w osobnym wierszu. Zawiera on trzy liczby naturalne a, b oraz k (0 ≤ a, b ≤ p-1, 1 ≤ k ≤ 10000). Liczby a i b to numery planet pomiędzy, którymi kursują statki danej linii, zaś k to koszt jej ewentualnej modernizacji.
Wyjście
W pierwszej i jedynej linii wyjścia należy wypisać szukany koszt inwestycji.
Przykład
Wejście:
4 6 0 1 100 0 1 18 1 2 40 0 2 70 2 3 2 3 2 11
Wyjście:
60
Dodane przez: | Maciej Boniecki |
Data dodania: | 2010-01-13 |
Limit czasu wykonania programu: | 1s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: NODEJS OBJC PERL6 SCM qobi SQLITE VB.NET |
Pochodzenie: | II Mistrzostwa WWSI w Programowaniu |