Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | renovare.in, renovare.out | Sursă | Autumn Warmup 2007, Runda 1 |
| Autor | Tiberiu Savin | Adăugată de |  Savin Tiberiu •devilkind |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 8192 kbytes |
| Scorul tău | N/A | Dificultate | N/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
Fisierului 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 ≤ 100
- 1 ≤ m ≤ 200
- Intr-un rezervor nu se poate stoca apa, cantitatea de apa care intra in rezervor trebuie sa fie egala cu cantitatea de apa care iesa.
- 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 232
Exemplu
| renovare.in | renovare.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
