Fişierul intrare/ieşire:renovare.in, renovare.outSursăAutumn Warmup 2007, Runda 1
AutorTiberiu SavinAdăugată dedevilkindSavin Tiberiu devilkind
Timp execuţie pe test0.7 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Renovare

Populatia orasului Galati a crescut foarte mult in ultimi ani iar infrastructura acestuia nu reuseste sa faca fata la numarul mare de locuitori. Orasul este alimentat cu apa de catre o statie de pompare aflata la cativa kilometri distanta, statie care pompeaza apa printr-o retea de tevi. Tevile sunt conectate intre ele prin rezervoare astfel ca o teava uneste 2 rezervoare, iar 2 tevi distincte comunica intre ele daca au un capat in acelasi rezervor. Fiecare teava este caracterizata de 4 numere: a , b , c , cst , avand urmatoarea semnificatie: prin teava respectiva se pot pompa c litri de apa de la rezorvorul a la rezervorul b. Daca platim nr*cst lei pentru renovarea tevii atunci vom putea pompa prin ea c+nr litri de apa. Se stie ca rezervorul numarul 1 reprezinta statia de pompare iar rezervorul numarul n reprezinta rezervorul de la care apa pleaca catre casele din oras. Misiunea dumneavoastra este sa aflati costul minim care trebuie platit pentru ca statia de pompare sa poate trimite catre oras x litri de apa.

Date de intrare

Pe prima linie a fisierului renovare.in se vor afla 3 numere n m x reprezentand numarul de rezervoare, numarul de tevi respectiv numarul de litri care trebuie pompati prin retea. Pe urmatoarele m linii se vor afla cate 4 numere reprezentand caracteristicile fiecarei tevi, numerele avand semnificatia din enunt.

Date de iesire

Fisierul renovare.out va contine un singur numar, costul minim care trebuie platit pentru ca reteaua sa poata transporta x litri de apa de la rezervorul 1 la rezervorul n.

Restrictii

  • 1 ≤ n ≤ 200
  • 1 ≤ m ≤ 2000
  • 1 ≤ x ≤ 200 000
  • Intr-un rezervor nu se poate stoca apa, cantitatea de apa care intra in rezervor trebuie sa fie egala cu cantitatea de apa care iese.
  • Capacitatea initiala a tevilor este mai mica sau egala cu 100
  • Costul de renovare a tevilor este mai mic sau egal cu 1000
  • Se garanteaza ca rezultatul va fi mai mic decat 2*109

Exemplu

renovare.inrenovare.out
6 7 11
1 2 3 2
1 3 2 3
1 4 1 2
4 5 1 3
2 3 6 2
3 6 5 2
5 6 1 10
22

Explicatie

Tevii care conecteaza rezervoarele 1 2 ii marim capacitata cu 3 unitatii, tevii care conecteaza rezervoarele 1 3 ii marim capacitatea cu 2, iar tevii care uneste rezervoarele 3 6 ii marim capacitatea cu 5 unitati. In acest fel costul total este:

2*3+3*2+5*2=22

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content