== include(page="template/taskheader" task_id="mine") ==
==Include(page="template/taskheader" task_id="mine")==
Poveste ...
Dupa ce si-a recuperat harta (eventual), Max Damage se gaseste din nou in masina urmarit de politisti. Pentru a scapa se hotaraste sa se ascunda intr-o mina parasita. Problema e ca innauntru este intuneric, iar de la atatea "acrosari" farurile nu mai lumineaza. El pune in functiune un vechi generator de electricitate pentru a lumina galeriile minei, insa acesta functioneaza ciudat si uneori ofera mai multa electricitate, alteori mai putina. Din fericire, Damage stie cum variaza cantitatea de energie electrica. El are de asemenea o harta a minei. Aceasta este formata din galerii care se unesc in intersectii. Intre doua intersectii pot exista oricate galerii, doua galerii nu se intalnesc decat in intersectii, iar o galerie poate fi parcursa in ambele directii. De asemenea Max stie pentru fiecare galerie care trebuie sa fie cantitatea minima de elecricitate produsa de generator pentru a fi parcursa in siguranta. Toate galeriile au aceeasi lungime si pot fi parcurse intr-un singur interval de timp (evident,
daca este destula lumina). Deci tot ce-i trebuie acum este un plan.
h2. Cerinta
...
Max vrea sa ajunga de la intrarea principala (intersectia numarul $1$) la iesirea de urgenta (intersectia numarul $N$), iar voi va trebui sa ii spuneti cat de repede poate face asta.
h2. Restrictii
h2. Date de Intrare
...
Din fisierul $mine.in$ se citesc pe prima linie $N$(numarul de intersectii) si $M$( numarul de galerii).
Pe urmatoarele $M$ linii se citesc cate $3$ numere $i j k$ cu semnificatia ca exista o galerie de la intersectia $i$ la intersectia $j$ iar cantitatea minima de electricitate necesara este $k$.
Pe linia urmatoare se gaseste $W$, urmata de $W$ valori. A $q-a$ valoare reprezinta cantitatea de energie electrica generata la momentul $q$.
h2. Date de intrare
h2. Date de Iesire
...
In fisierul $mine.out$ se va scrie un singur numar $t$, timpul minim in care Max poate iesi din mina, sau $-1$ daca nu are nici o sansa.
h2. Date de iesire
h2. Restrictii si observatii
...
* $1 ≤ N ≤ 10^4$
* $1 ≤ M ≤ 10^5$
* &1 ≤ W ≤ 10^6$
* capacitatea minima de electricitate pentru o muchie este cuprinsa intre $0$ si $10^9$
* Max Damage poate astepta oricat timp intr-o intersectie
* Daca sirul de $W$ valori se termina, generatorul se opreste si nimeni nu vrea sa ramana intr-o mina parasita pe intuneric (chiar daca ultimele galerii pana la iesire au valoarea $k$ egala cu $0$)
h2. Exemplu
| mine.in | mine.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. mine.in |_. mine.out |_. Explicatie |
| 3 2
1 2 5
2 3 10
5
2 6 9 10 0
| 4
| Max ramane la timpul 1 in intersectia 1, la timpul 2 se deplaseaza in intersectia 2, la timpul 3 sta pe loc, iar la timpul 4 se deplaseaza in intersectia 3. |
== include(page="template/taskfooter" task_id="mine") ==
==Include(page="template/taskfooter" task_id="mine")==
