În cadrul organizatiei
Algola s-a declarat stare de urgenta. Toti membrii sai, aflati în diferite
orase din tara, trebuie sa ajunga cât 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 sediul central. Strazile ce conecteaza orasele sunt bidirectionale
si fiecare strada poate fi parcursa într-o unitate de timp de oricare
membru Algola. Fiecare strada are o limita de siguranta care indica numarul
maxim de membri ce pot circula într-o unitate de timp pe acea strada.
Parcurgerea unei strazi poate începe numai la momente de timp întregi.
Cerinta
Fiind data harta oraselor, precum si numarul de membri ai organizatiei aflati
în 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).
Date de intrare
Prima linie a fisierului algola.in
contine doua numere întregi separate printr-un spatiu, N si M, reprezentând
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, A1 A2 … AN, unde Ai reprezinta
numarul de membri din orasul i. Urmatoarele M linii contin câte trei numere
întregi separate prin spatii, X Y L, cu semnificatia: între orasele
X si Y exista o strada a carei limita de siguranta este L.
Date de iesire
Fisierul de iesire algola.out
va contine o singura linie numarul T reprezentând timpul minim în
care toti membrii organizatiei ajung la sediul central.
Restrictii si precizari
1 <= N <= 50
1 <= M <= 300
Timpul de parcurgere al unui oras este 0
Între doua orase exista cel mult o strada
Toti membrii pot ajunge la sediu central
Limitele de siguranta ale strazilor sunt numere întregi 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 ramâne în orice oras pe o perioada nelimitata
de timp
Pentru 20% din teste drumul de la fiecare oras la sediu este unic; pentru înca
30% din teste numarul total de membri ai organizatiei va fi maxim 4
Exemplu
| algola.in | algola.out |
| 4 4 0 5 6 5 1 2 3 1 3 5 4 2 2 4 3 5 |
2 |
Timp maxim de executie/test:
0.3 secunde sub sistemul de operare Linux
Limita de memorie: 31 Mb din care 1 Mb pentru segmentul de stiva
stud. Silviu
Ganceanu
Universitatea "Politehnica" Bucuresti