algola

Algola

== include(page="template/taskheader" task_id="algola") ==

==Include(page="template/taskheader" task_id="algola")==

Poveste ...

In cadrul organizatiei Algola s-a declarat stare de urgenta. Toti membrii sai, aflati in diferite orase din tara, trebuie sa ajunga cat mai rapid la sediul central. Cele $N$ orase de pe harta tarii sunt numerotate cu numerele de la $1$ la $N$, orasul $1$ fiind locatia sediului central. Strazile ce conecteaza orasele sunt bidirectionale si fiecare dintre strazi poate fi parcursa intr-o unitate de timp de oricare membru Algola. Fiecare strada are o limita de siguranta care indica numarul maxim de membri ce pot circula intr-o unitate de timp pe acea strada. Parcurgerea unei strazi poate incepe numai la momente de timp intregi.

h2. Cerinta

...
 
h2. Restrictii
 
...

Fiind data harta oraselor, precum si numarul de membrii ai organizatiei aflati in fiecare oras, sa se calculeze timpul minim $T$ necesar acestora pentru a ajunge la sediul central ({$T$} va fi momentul la care ajunge ultimul membru la sediul central).

h2. Date de intrare

...

Prima linie a fisierului $algola.in$ contine doua numere intregi separate printr-un spatiu, $N$ si $M$, reprezentand numarul de orase de pe harta si numarul de strazi dintre ele. Pe cea de-a doua linie se vor afla N numere separate prin spatii, $A{~1~} A{~2~} ... A{~N~}$ unde $A{~i~}$ reprezinta numarul de membri din orasul $i$. Urmatoarele $M$ linii contin cate trei numere intregi separate prin spatii, $X Y L$, cu semnificatia: intre orasele $X$ si $Y$ exista o strada a carei limita de siguranta este $L$.

h2. Date de iesire

...

Fisierul de iesire $algola.out$ va contine o singura linie numarul $T$ reprezentand timpul minim in care membrii organizatiei ajung la sediul central.
 
h2. Restrictii si precizari
 
* $1 ≤ N ≤ 50$
* $1 ≤ M ≤ 300$
* Timpul de parcurgere al unui oras este $0$
* Totii membrii vor putea ajunge la sediu central
* Limitele de siguranta ale strazilor sunt numere intregi pozitive din intervalul $[1,10]$
* Toti membrii organizatiei afla de starea de urgenta la momentul $0$
* Organizatia are cel mult $50$ de membri
* Membrii organizatiei pot ramane in orice oras pe o perioada nelimitata de timp
* Pentru $20%$ din teste drumul de la fiecare oras la sediu este unic; pentru inca $30%$ din teste numarul total de membri ai organizatiei va fi maxim $4$

h2. Exemplu

| algola.in | algola.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="algola") ==

table(example). |_. algola.in |_. algola.out |
| 4 4
0 5 6 5
1 2 3
1 3 5
4 2 2
4 3 5 | 2 |
 
==Include(page="template/taskfooter" task_id="algola")==
 
 

427