Fişierul intrare/ieşire:foametea.in, foametea.outSursăFMI No Stress 9
AutorStefan RaduAdăugată defminostress9FMI No Stress 9 fminostress9
Timp execuţie pe test0.4 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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 care îi rămân în traistă după ce consumă cantitatea necesară parcurgerii drumului respectiv. 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
  • 0 ≤ si ≤ K
  • 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.infoametea.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. 

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?