Renovare

renovare

== include(page="template/taskheader" task_id="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.

Poveste si cerinta...

h2. 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.

...

h2. 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$.

...

h2. 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*10^9^$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. 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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. 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$
 
 

...

== include(page="template/taskfooter" task_id="renovare") ==

2104