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

 

Fişierul intrare/ieşire:pitici.in, pitici.outSursălot 2006
AutorDan-Ionut FecheteAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.225 secLimită de memorie20096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Pitici

In varful muntelui Acrom traiesc pe timpul verii K pitici, numerotati de la 1 la K. Pe munte exista N cabane, aflate la altitudini diferite, legate intre ele de M poteci. Cabana piticilor este numerotata cu 1, iar cabana de la poalele muntelui cu N. Fiindca iarna este prea frig, piticii se muta in cabana de la poalele muntelui, unde este mai cald. Piticii sunt disciplinati si coboara de pe munte in ordinea crescatoare a numerelor lor. Pentru a nu fi acuzati de lipsa de personalitate, fiecare pitic alege drumul cel mai scurt pana jos, drum diferit de fiecare dintre drumurile alese de piticii ce au coborat inaintea lui. Un drum al unui pitic este o succesiune de cabane x1 x2 ... xp cu proprietatea ca x1=1, xp=N si intre oricare doua cabane consecutive pe drum xi si xi+1 exista o poteca ce merge in vale (adica altitudinea cabanei xi este mai mare decat altitudinea cabanei xi+1). Doua drumuri sunt diferite daca exista cel putin o cabana ce apartine unuia dintre drumuri si nu apartine celuilalt. Lungimea unui drum este suma lungimilor potecilor ce leaga cabanele situate pe acest drum.

Cerinta

Scrieti un program care sa determine lungimea drumului ales de fiecare pitic, drum ce respecta conditiile din enunt.

Date de intrare

Pe prima linie a fisierului de intrare pitici.in sunt scrise trei numere naturale N M K separate prin cate un spatiu cu semnificatia din enunt. Urmatoarele M linii contin cate 3 numere a b c separate prin cate un spatiu, cu semnificatia ca exista poteca de la cabana a la cabana b de lungime c, cabana a avand o altitudine mai mare decat cabana b.

Date de iesire

...

Restrictii

  • ... ≤ ... ≤ ...

Exemplu

pitici.inpitici.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicatie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?