Eu
locuiesc in orasul Iasi (sa-l notam pentru simplitate orasul A)
si trebuie sa ajung in decurs de maxim T
ore in Bucuresti (sa-l notam orasul B).
Eu nu circul decat pe autostrada, cu viteza maxima legala, asa ca am luat o
harta pe care sunt marcate cele N
orase din tara, precum si cele M
autostrazi ce realizeaza legatura dintre orase. Fiecare autostrada face legatura
intre doua orase.
Harta este foarte detaliata si prezinta si taxele de autostrada si costul parcarii
in fiecare oras.
In orasul meu (A) si in
orasul destinatie (B)
eu nu platesc parcarea, dar daca vreau sa opresc in orice alt oras, trebuie
sa platesc o taxa de parcare (de exemplu, pentru orasul i,
taxa de parcare va fi piRON/ora).
Taxele de autostrada difera in functie de momentul in care intru pe autostrada.
Taxa se plateste pentru fiecare ora de mers pe autostrada, deci daca am mers
pe o autostrada h ore
si la momentul intrarii pe autostrada taxa era c,
la iesirea de pe autostrada voi plati c*h
RON.
Cerinta
Scrieti
un program care sa determine suma totala minima (care reprezinta cost parcari
+ cost taxe de autostrada) pe care trebuie sa o platesc pentru a ajunde din
orasul A in orasul B
in maxim T ore.
Date
de intrare
Fisierul
de intrare auto2.in contine
pe prima linie doua numere naturale separate printr-un spatiu N
M, reprezentand numarul de orase, respectiv, numarul de autostrazi.
Pe cea de a doua linie se afla 3 numere naturale separate prin spatiu A
B T, reprezentand orasul de plecare, orasul destinatie si timpul
maxim in care trebuie sa ajung la destinatie.
Pe a treia linie se afla N
numere naturale separate prin cate un spatiu p1
p2 ... pn, reprezentand costul de parcare/ora
in fiecare dintre cele N
orase.
Pe urmatoarele 2*M linii
se afla informatii despre cele M
autostrazi, care 2 linii pentru o autostrada. Pe prima linie dintre cele doua
sunt scrise 3 numere naturale separate prin cate un spatiu O1
O2 D, cu semnificatia "autostrada leaga orasele O1
si O2, si parcurgerea
ei dureaza D ore la viteza
maxima legala". Pe cea de a doua linie sunt scrise T
numere naturale separate prin cate un spatiu c0
c1 ... cT-1, unde ci
reprezinta costul pentru o ora de mers pe autostrada respectiva, daca am intrat
la momentul i.
Date de iesire
Fisierul
de iesire auto2.out va
contine o singura linie pe care va fi scris un singur numar natural, reprezentand
suma totala minima pe care trebuie sa o platesc pentru a ajunge din orasul A
in orasul B.
Restrictii si precizari
0 < N, T <= 100
M <= 500
0 <= pi,
ci <= 100
Eu plec din orasul A
la momentul 0.
Intre doua orase exista
cel mult o autostrada.
Exemplu
auto2.in
auto2.out
Explicatie
3
2
1 3 5
0 1 0
1 2 2
2 5 5 5 5
2 3 2
5 5 5 1 5
7
Plec din orasul 1
la momentul 0, merg pe autostrada 1 2 timp de 2 ore (deci platesc 2*2=4
RON).
Am ajuns in orasul 2 la momentul 2. Parchez aici o ora si platesc 1 RON.
Apoi intru pe autostrada 2 3
pe care merg doua ore (deci platesc 2*1 RON). In total 7 RON.