Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2020-04-10 08:01:35.
Revizia anterioară   Revizia următoare  

 

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.2 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 (în limita valorii K) la fiecare vizită pe care i-o face. 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 momentul respectiv în traistă. 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 mătuşa din fiecare dintre cele N oraşe).
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 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 teste în valoare de 30 de puncte se garantează că C = 0 pentru toate drumurile.
  • În fiecare oraş Fomistul poate alege să mănânce oricâte sarmale între 0 şi si cu condiţia 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
159
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
3374

Explicaţie

1. Fomistul mănâncă 4 sarmale în primul oraş, ajunge în oraşul 3 în 7 * (1 + 42) = 119, iar apoi în oraşul 5 în 119 + 8 * (1 + 22) = 159.
2. Fomistul nu poate ajunge în oraşul 5. 

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?