drum-bugetat

Drum bugetat

== include(page="template/taskheader" task_id="drum-bugetat") ==

Poveste şi cerinţă...

A fost odata ca niciodata tinutul lui Rosu Imparat, unde traiau Harap-Alb si Ileana Cosanzeana care, fiind indragostiti, se intalneau foarte des desi stateau in orase diferite.
La inceput totul a fost perfect, intrucat Harap-Alb era un tanar destept si stia sa aleaga drumul cel mai scurt pana la casa Ileanei folosind algoritmii invatati la facultate.
Totusi, situatia s-a schimbat de cand imparatul Rosu a decis sa taxeze trecerea prin orase cu un numar de galbeni. Astfel, Fat-Frumos si-a dat seama ca bugetul personal nu ii ajunge intotdeauna daca foloseste cel mai scurt drum pentru a ajunge la Ileana Cosanzeana.
Stiind ca Fat-Frumos stie perfect harta imparatiei data prin $N$ - numarul de orase, si $M$ - numarul de drumuri directe intre orase pe care se poate circula in ambele sensuri, si avand la dispozitie bugetul de care dispune Fat-Frumos pentru a calatori, $B$, ajutati-l sa descopere cum poate ajunge pana in orasul unde locuieste Ileana Cosanzeana, t, stiind ca la inceput Fat Frumos este in orasul s. Pentru ca vrea sa o vada pe Ileana cat mai repede, Fat-Frumos prefera sa foloseasca cea mai scurta cale pentru care are bugetul necesar pentru a plati taxele de transport din fiecare oras prin care trece (mai putin sursa, dar incluzand destinatia). Daca exista mai multe astfel de drumuri, evident ca el va prefera drumul cel mai ieftin pentru ca ii raman mai multi bani pentru a iesi in oras cu prietena lui.

h2. Date de intrare

Fişierul de intrare $drum-bugetat.in$ ...

Fisierul de intrare $drum-bugetat.in$ contine:

h2. Date de ieşire

* pe primul rand se afla trei numere intregi: $N$ - numarul de orase, $M$ - numarul de drumuri directe intre orase, si $B$ - numarul de galbeni pe care ii are la dispozitie Fat-Frumos .
* pe al doilea rand se afla alte doua numere intregi: $s$ - orasul in care se afla Harap-Alb, si $t$ - orasul in care se afla Ileana Cosanzeana.
* pe urmatorul rand se afla $N$ numere intregi care reprezinta costurile de trecere (numarul de galbeni care trebuie platiti) prin cele $N$ orase (primul oras apare la inceput, orasul $N$ este ultimul).
* pe urmatoarele $M$ randuri sunt $3$ numere: primele doua reprezinta orasele intre care exista acest drum direct, iar al treilea este lungimea drumului respectiv.

În fişierul de ieşire $drum-bugetat.out$ ...

h2. Date de iesire

h2. Restricţii

In fisierul de iesire $drum-bugetat.out$ scrieti o linie pe care se afla doua numere intregi separate printr-un spatiu:

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

* lungimea drumului cel mai scurt care poate fi folosit de Fat-Frumos
* numarul de galbeni pe care Fat-Frumos ii cheltuieste pentru a alege drumul respectiv

h2. Exemplu

h2. Restrictii

table(example). |_. drum-bugetat.in |_. drum-bugetat.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

* $0 ≤ N ≤ 1000$
* $0 ≤ M ≤ 10000$
* $0 ≤ B ≤ 1000$
* lungimea unui drum direct intre $2$ orase adiacente : $0$ .. $1000$
* taxa pentru a trece printr-un oras: $0$ .. $B$
 
h2. Observatii

h3. Explicaţie

* In fisierul de intrare, orasele sunt numerotate de la $1$ la $N$.
* Daca nu exista nici un drum se afiseaza @"-1"@ (fara ghilimele).

...

h2. Exemplu
 
table(example). |_. drum-bugetat.in |_. drum-bugetat.out |
| 7 9 4
  1 7
  0 1 2 10 1 3 0
  1 2 1
  1 3 3
  2 4 1
  2 5 5
  3 5 1
  3 6 2
  4 7 1
  5 7 5
  6 7 2
| 9 3
|

== include(page="template/taskfooter" task_id="drum-bugetat") ==
 

== include(page="template/taskfooter" task_id="drum-bugetat") ==

8868