Fişierul intrare/ieşire:mine.in, mine.outSursăPACO 2006
AutorSorin Stancu-MaraAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Mine

Dupa ce si-a recuperat harta, 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 inauntru 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.

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.

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.

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.

Restrictii si observatii

  • 1 ≤ N ≤ 104
  • 1 ≤ M ≤ 105
  • 1 ≤ W ≤ 106
  • Capacitatea minima de electricitate pentru o muchie este cuprinsa intre 0 si 109
  • 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)

Exemplu

mine.inmine.out
3 2
1 2 5
2 3 10
5
2 6 9 10 0
4

Explicatie

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content