Ion s-a îndragostit de Maria si doreste sa o viziteze cât mai des
posibil. Ion locuieste în orasul Iasi, iar Maria locuieste în Lugoj.
Ion calatoreste întotdeauna cu masina sa, care consuma 1dl de benzina
/km. Rezervorul masinii are o capacitate de K dl. De la Iasi la Lugoj sunt M drumuri diferite si câteva puncte de intersectie notate 1,2,…,N. Iasi,
orasul de plecare a fost notat cu 1, iar Lugoj, orasul de sosire a fost notat
cu N. În fiecare dintre cele N puncte de intersectie sunt statii de benzina,
dar pretul benzinei poate sa difere de la o statie la alta.
Cerinta
Scrieti un program care sa determine cel mai scurt drum de la Iasi la Lugoj
si o strategie de a cheltui pe acest drum cât mai putini bani pe benzina.
Date de intrare
Fisierul de intrare se numeste lover.in.
Prima linie a fisierului de intrare contine 3 numere naturale N M K. În
fiecare dintre urmatoarele M linii se gasesc 3 numere naturale X Y D, reprezentând
distanta D exprimata în km de la punctul de intersectie X la punctul de
intersectie Y. Fiecare dintre urmatoarele N-1 linii contine un numar natural Pi
reprezentand pretul benzinei in statia i.
Date de iesire
Fisierul de iesire lover.out
are o singura linie pe care afisati, separate prin spatiu, doua numere lg sum (lungimea
celui mai scurt drum de la Iasi la Lugoj si suma minima cheltuita pe benzina).
Restrictii
N <= 3000 este un numar natural care reprezinta numarul
de puncte de intersectie.
Pi <= 1000 (1 <= i <= N-1) sunt numere naturale, Pi
reprezinta pretul pentru 1 dl de benzina la statia i.
M <= 11000 este un numar natural care reprezinta numarul
de drumuri existente între cele N puncte de intersectie.
K <= 300 este un numar natural care reprezinta capacitatea
rezervorului masinii, exprimata în dl.
La fiecare statie de benzina exista o cantitate suficient de mare de benzina.
Doua puncte de intersectie pot fi conectate printr-un singur drum.
În datele de test exista un singur drum minim.
Exemplu
lover.in
lover.out
4 5 6
1 2 5
1 3 4
3 2 2
2 4 2
3 4 5
5
10
8
7
40
prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi