Fişierul intrare/ieşire:algola.in, algola.outSursăFinala .campion 2005
AutorSilviu-Ionut GanceanuAdăugată de
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inalgola.out
4 4
0 5 6 5
1 2 3
1 3 5
4 2 2
4 3 5
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content