Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | algola.in, algola.out | Sursă | Finala .campion 2005 |
| Autor | Silviu-Ionut Ganceanu | Adăugată de | |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |  5/5 |
Vezi solutiile trimise | Statistici
Algola
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.
Cerinta
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).
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, A1 A2 ... AN unde Ai 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.
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.
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
Exemplu
| algola.in | algola.out |
|---|---|
| 4 4 0 5 6 5 1 2 3 1 3 5 4 2 2 4 3 5 | 2 |
