student
   

Zadania koła algorytmicznego

124 prac Herkulesa

Herkules 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.


Autor:Przemysław Gordinowicz
Data publikacji:2005-02-15
 

Konsultacje  

Ważne info:
Koło algorytmiczne
spotkania w PON o 12.00h sala sanów

Ważne info:
Zawody algorytmiczne
już 28 października 2005 - jedź z nami!

Chcę otrzymywać newsy:
Podaj swój mail:

 

 


student site & engine by DONE

 

wszelkie pytania proszę kierować pod adres r.papis@done.pl
 

 

DONE