Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | foametea.in, foametea.out | Sursă | FMI No Stress 9 |
| Autor | Stefan Radu | Adăugată de |  FMI No Stress 9 •fminostress9 |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Foametea
Fomistul nostru preferat locuieşte într-o ţară cu N oraşe conectate prin M drumuri unidirecţionale. Fiecare drum din ţara sa are o anumită lungime, Li şi o anumită dificultate Ci, egală cu numărul de sarmale pe care Fomistul trebuie să le consume la începerea deplasării pe respectivul drum pentru a-l putea parcurge cu succes. Acesta poate căra în traistă maxim K sarmale şi, din fericire, în fiecare oraş cunoaşte câte o mătuşă care îi oferă maxim si sarmale la fiecare vizită a sa în oraşul cu pricina. Este bine cunoscut faptul că timpul necesar parcurgerii unui drum de lungime L este egal cu L * (S2 + 1), unde S este numărul de sarmale pe care le cară în traistă pe acel drum. Fomistul, pentru că îi este prea foame pentru a se descurca singur, vă roagă să îi spuneţi cât de repede poate ajunge la cina festivă din oraşul N (unde se vor servi sarmale), plecând din oraşul 1.
Date de intrare
Fişierul de intrare foametea.in va conţine pe prima linie numerele N (numărul de oraşe), M (numărul de drumuri), K (capacitatea traistei Fomistului).
Următoarea linie va conţine numerele s1, s2, ..., sN (numărul maxim de sarmale oferit de fiecare dintre cele N mătuşi).
Următoarele M linii vor conţine fiecare câte 4 întregi, A, B, L, C semnificând că există un drum ce pleacă din oraşul A, ajunge în oraşul B, are lungimea L şi poate fi parcurs de Fomist consumând C sarmale.
Date de ieşire
Fişierul de ieşire foametea.out va conţine o singură linie cu răspunsul la întrebarea Fomistului.
În cazul în care acesta nu poate ajunge la cina festivă afişaţi mesajul "Fomistul moare de foame" (fără ghilimele).
Restricţii
- 1 ≤ N ≤ 5000
- 1 ≤ M ≤ 25000
- 0 ≤ K ≤ 30
- 1 ≤ A, B ≤ N
- 0 ≤ L ≤ 10000
- 0 ≤ C ≤ K
Precizări
- Pentru teste în valoare de 20 puncte se garantează că L = 1 şi că C = 0 pentru toate drumurile.
- Pentru alte teste în valoare de 20 puncte se garantează că C = 0 pentru toate drumurile şi că nu există cicluri (graful rezultat este un DAG).
- Pentru alte teste în valoare de 30 de puncte se garantează că C = 0 pentru toate drumurile.
- Pentru alte teste în valoare de 30 de puncte se aplică restricţiile iniţiale.
- În fiecare oraş i, Fomistul poate alege să introducă în traistă oricâte sarmale între 0 şi si, cu condiţia ca numărul total să nu depăşască limita de K.
- Fomistul are iniţial 0 sarmale în traistă. Va lua cât consideră de cuviinţă de la mătuşa din primul oraş.
Exemplu
| foametea.in | foametea.out |
|---|---|
| 5 3 5 4 3 0 2 0 5 4 0 2 3 5 8 2 1 3 7 2 | 43 |
| 5 3 5 2 3 1 0 1 2 1 5 4 1 5 2 4 1 4 5 4 | Fomistul moare de foame |
| 6 10 24 24 11 15 8 16 23 2 6 2 19 1 3 5 0 5 4 3 12 2 5 4 12 4 2 5 9 3 5 3 21 1 2 5 15 3 2 3 23 3 4 4 20 6 1 3 14 | 327 |
Explicaţie
ex. 1:
Fomistul îşi încarcă în traistă 4 sarmale din primul oraş.
Se pregăteşte de drumul (1, 3) mâncând 2 dintre sarmalele din traistă şi ajunge în oraşul 3 în 7 * (1 + 22) = 35 unităţi de timp.
În oraşul 3 nu i se oferă nicio sarma.
Se pregăteşte de drumul (3, 5) mâncând 2 sarmale şi ajunge în oraşul 5 după încă 8 * (1 + 02) = 8 momente de timp.
Răspunsul final este, aşadar 35 + 8 = 43.
ex. 2:
Fomistul nu poate ajunge în oraşul 5.
