== include(page="template/taskheader" task_id="dcmcp") ==
Poveste si cerinta...
Sa consideram un graf neorientat avand $N$ noduri, numerotate de la $1$ la $N$, si $M$ muchii. Nodul $1$ corespunde unei mine de unde sunt extrase niste minerale pretioase. Nodul $N$ corespunde unei fabrici de prelucrare a mineralelor. Fiecare muchie are asociate o durata de traversare (exprimata in unitati de timp) si o capacitate (exprimata in unitati de minerale). S-a decis ca mineralele extrase din mina sa fie transportate la fabrica folosind un singur drum. Acest drum trebuie sa aiba cea mai mare capacitate posibila, pentru a putea transporta simultan cat mai multe unitati de minerale. Capacitatea unui drum este egala cu capacitatea minima a unei muchii de pe drum. Deoarece mineralele sunt foarte sensibile, ele se vor descompune dupa $T$ unitati de timp de la extragerea acestora din mina. Prin urmare, durata totala de traversare a drumului ales (suma duratelor de traversare ale muchiilor de pe drum) trebuie sa fie mai mica sau egala cu {$T$}.
h2. Date de intrare
...
Prima linie a fisierului de intrare $dcmcp.in$ contine un numar intreg $X$, reprezentand numarul de teste ce urmeaza. Prima linie a fiecarui test contine $3$ numere intregi, separate prin spatii: $N$, $M$ si $T$. Fiecare din urmatoarele $M$ linii va contine $4$ numere intregi, separate prin spatii: $A$, $B$, $C$ si $D$, avand semnificatia ca exista o muchie intre nodurile $A$ si $B$, avand capacitatea $C$ si durata de traversare $D$. $A$ si $B$ sunt numere intregi diferite intre $1$ si $N$.
h2. Date de iesire
...
Pentru fiecare din cele $X$ teste, in ordinea din fisierul de intrare, veti afisa in fisierul de iesire $dcmcp.out$ cate o linie continand capacitatea maxima a unui drum de la mina la fabrica, avand proprietatile cerute.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ X ≤ 10$
* $2 ≤ N ≤ 10 000$
* $1 ≤ M ≤ 50 000$
* $1 ≤ T ≤ 500 000$
* $1 ≤ capacitatea oricarei muchii ≤ 2 000 000 000$
* $1 ≤ durata de traversare a oricarei muchii ≤ 50 000$
* Va exista cel mult o muchie intre oricare $2$ noduri.
h2. Exemplu
table(example). |_. dcmcp.in |_. dcmcp.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|2
2 1 10
1 2 13 10
4 4 20
1 2 1000 15
2 4 999 6
1 3 100 15
3 4 99 4
|13
99
|
h3. Explicatie
...
== include(page="template/taskfooter" task_id="dcmcp") ==
