Soarta lui Vasile a fost crunta. Dupa câteva aventuri
de tip Caritas a ajuns un biet homeless. Acum e inca iarna, e frig si
Vasile s-a gândit ca ar fi bine sa isi cumpere un abonament CFR, macar
sa poata dormi in vagoane incalzite si sa viseze la o viata mai buna.
Vasile a analizat harta CFR si a identificat N
statii de cale ferata (pe care le-a numerotat de la 1
la N) si P
tronsoane de cale ferata. Un tronson realizeaza legatura bidirectionala intre
doua statii, lungimea unui tronson fiind egala cu timpul necesar trenului sa
ajunga dintr-o statie in cealalta.
De asemenea Vasile a studiat si mersul trenurilor si cunoaste
pentru fiecare tren timpul la care pleaca din prima statie de pe ruta sa (exprimat
in secunde) si statiile prin care trece. Trenurile opresc in toate statiile
prin care trec, timpul de stationare fiind neglijabil. Când doua trenuri
se afla in aceeasi statie, Vasile poate sa sara dintr-un tren in altul, fara
a pierde timp suplimentar.
Initial (secunda 1)
Vasile se afla in statia cu numarul 1.
Vasile pleaca din statia 1
si trebuie sa se intoarca in statia 1
in intervalul de timp [T1,
T2], timpii T1
si T2 fiind exprimati
in secunde. El se deplaseaza numai cu trenul, poate cobori din tren in orice
statie prin care trece trenul respectiv, se poate urca intr-un tren in oricare
dintre statiile prin care trece trenul respectiv (cu conditia ca Vasile sa se
afle in statie la momentul in care trenul soseste).
Cerinta
Scrieti un program care sa determine timpul total
minim de asteptare in statii, in conditiile in care Vasile trebuie sa calatoreasca
cu trenurile existente si sa revina in statia 1
in intervalul de timp [T1,
T2].
Date de intrare
Fisierul de intrare homeless.in
contine:
- pe prima linie 5 numere intregi N P V T1 T2, separate prin spatii (N
reprezinta numarul de statii, P
este numarul de tronsoane, V
este numarul de trenuri, iar T1
si T2 au semnificatia
din enuntul problemei). - fiecare dintre urmatoarele P
linii contine informatii despre un tronson sub forma a 3 numere intregi separate
prin spatii S1 S2 T
cu semnificatia "tronsonul leaga statiile S1
si S2, durata calatoriei
pe acest tronson fiind T
secunde". - fiecare dintre urmatoarele V
linii contine informatii despre un tren. Primul numar de pe linia corespunzatoare
unui tren este T0,
care reprezinta timpul de plecare a trenului din prima statie (exprimat in secunde),
al doilea numar este NS
care reprezinta numarul de statii de pe ruta acestui tren (inclusiv statia de
plecare si cea de sosire), iar urmatoarele NS
numere reprezinta in ordine numerele statiilor prin care trece trenul. Trenul
pleaca de la prima statie si se opreste la ultima statie de pe ruta sa, iar
la ultima statie toti calatorii trebuie sa coboare. Toate numerele de pe linie
sunt separate prin câte un spatiu.
Date de iesire
Fisierul de iesire homeless.out
va contine o singura linie pe care va fi scris timpul total minim de asteptare
in statii.
Restrictii
1 < N, V < 1001
0 < T1 <= T2 <= 50000
0 < durata calatoriei pe orice tronson T < 601
0 < numarul de statii de pe ruta oricarui tren NS < 1001