|
Zadania koła algorytmicznego124 prac HerkulesaHerkules ma wykonać k zadań (każde tylko raz). Wykonanie każdego z zadań zajmuje pewną ilość czasu, który może się zmieniać wskutek wykonania innego zadania. Zależności między zadaniami są symetryczne, tzn. jeżeli wykonanie zadania x umożliwia zamianę czasu wykonania zadania y do t czasu to również wcześniejsze wykonanie zadania y zmieniło by czs wykonania zadania x do t. Czasy wykonania zadań jednak nigdy nie rosną. Zadanie Wyznaczyć minimalny czas potrzebny do wykonania wszystkich zadań. Wejście W pierwszym wierszu podana jest jedna liczba liczba k - liczba prac do wykonania (2<=k<=20736) W drugin znajduje się dokładnie k liczb całkowitych z zaktesu [1, 100 000] - są to wstępne czasy wykonania każdego z kzadań. W kolejnym znajduje się liczba m (0≶=m≶=2 000 000) - liczba zależności między zadaniami. W kolejnych m wierszach znaduje się m zależności - każda podana 3 liczbami: nr1 nr2 t - odpowiednio dwa numery zadań ( z zakresu [1, k] i czas do jakiego można skrócić wykonanie zadania. Wyjście Jedna liczba - czas wykoanania wszystkich prac Herkulesa.
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
wszelkie pytania proszę kierować pod adres r.papis@done.pl |