Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-02-08 11:55:34.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:fear.in, fear.outSursăWinter Challange, Runda 01, clasele 11-12
AutorSorin Stancu-MaraAdăugată defireatmyselfBogdan-Alexandru Stoica fireatmyself
Timp execuţie pe test0.225 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Fear

Desi Max Damage a plecat de mult din oras, reputatia lui este nestirbita, iar locuitorilor inca le este frica de posibila sa reintoarcere. Bineinteles, nimanui nu ii este mai frica decat sefului politiei. De aceea, Damage s-a gandit sa testeze cat de adanc a ramas in constiinta locuitorilor. El are harta orasului, care este format din n intersectii si m strazi bidirectionate, putand sa se ajunga dintr-o intersectie in oricare alta. Initial, eroul nostru se afla la poarta orasului (intersectia cu numarul 1) si vrea sa trimita zvonul reintoarcerii sale pana la casa sefului politiei (intersectia cu numarul n). Din pacate, pe o strada, frica nu se raspandeste de capul ei, ci nu poate depasi o anumita valoare reala (calculata, pentru strada respectiva, in functie de numarul de locuitor, media de varsta, speranta de viata, etc.). Mai mult, frica ce pleaca dintr-o intersectie se poate imprastia pe fiecare din strazile incidente, dar suma valorilor fricii de pe fiecare strada nu depaseste valoarea fricii din intersectie. De asemenea, valoarea fricii dintr-o intersectie este numeric egala cu suma valorilor de pe fiecare strada incidenta acesteia.
Cunoscand acestea, ajutati-l pe Max Damage sa determine valoarea maxima a fricii care poate ajunge in intersectia n.

Date de intrare

Pe prima linie a fisierului fear.in se afla n si m. pe urmatoarele M linii se gasesc cate 3 numare a, b si c, reprezentand ca pe o strada intre orasele a si b frica se poate raspandi cu maxim valoarea c.

Date de iesire

Rezultatul se afiseaza in fear.out, pe o singura linie, cu 4 zecimale.

Restrictii

  • 1 ≤ n ≤ 200
  • 1 ≤ m ≤ 19900
  • 1 ≤ c ≤ 200256
  • 1 ≤ factorul de frica maxim dintr-o intersectie ≤ 2147483647

Exemplu

fear.infear.out
3 3
1 2 5
1 3 7
2 3 4
28
4 4
1 4 10
2 4 5
2 3 5
3 4 5
10

Explicatie

Pentru primul exemplu, de la 1 la 3 se transimte frica cu factor 7, de la 1 la 2 cu factor 5 iar de la 2 la 3 cu factor 4, 7*4 = 28.
Pentru al doilea exemplu, desi daca am trimit frica si prin ciclul 4 3 2 4 am obtine un factor de frica mai mare de 10, trebuie sa ne oprim in 4.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?