Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | amenzi.in, amenzi.out | Sursă | Unirea 2007 |
| Autor | Adrian Diaconu | Adăugată de |  Adrian Diaconu •DITzoneC |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20096 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Vezi solutiile trimise | Statistici
Amenzi
Ion este politist intr-un mare oras. In oras exista N intersectii legate intre ele prin intermediul a M strazi pe care se poate circula in ambele sensuri. Pentru fiecare strada se stie timpul Ci necesar pentru a o parcurge. Informat de o sursa sigura Ion stie ca in cursul urmatoarei zile se vor petrece K infractiuni. Pentru fiecare infractiune i se cunosc urmatoarele date: Ti - timpul la care infractiunea are loc, Ai - intersectia in care infractiunea are loc, Si - amenda pe care Ion o poate da daca se afla in intersectia Si la momentul Ti.
Stie ca in cursul zilei urmatoare trebuie sa se intalneasca cu sotia sa, dar nu mai stie exact nici timpul nici ora la care trebuie sa faca acest lucru. Tot ce isi aminteste sunt P perechi de forma Xi, Yi care semnifica faptul ca s-ar putea sa trebuiasca sa se intalneasca cu sotia sa la momentul Yi in intersectia Xi.
Avand la dispozitie toate aceste date ajutati-l pe Ion sa afle valoare maxima totala a amenzilor pe care o poate da pentru fiecare din cele P perechi pe care si le aminteste. Din momentul in care se intalneste cu sotia sa Ion nu va mai da amenzi.
Date de intrare
Pe prima linie a fisierului de intrare amenzi.in se afla patru numere intregi N, M, K si P cu semnificatia din enunt. Urmatoarele M linii contin cate trei numere a, b si c cu semnificatia ca exista o strada ce leaga intersectiile a si b si care poate fi parcursa in c unitati de timp. Urmatoarele K linii contin cate trei numere a, b si c cu semnificatia ca va avea loc o infractiune in intersectia a, la timpul b si pentru care se va da o amenda in valoare de c unitati monetare. Apoi urmeaza P linii cu cate doua numere a si b cu seminficatia ca este posibil ca Ion sa se intalneasca cu sotia sa in intersectia a la momentul b.
Date de iesire
In fisierul de iesire amenzi.out vor exista P linii coninand valoarea totala maxima pe care Ion o va obtine din amenzi in fiecare din cele P cazuri descrise in fisierul de intrare. Daca Ion nu poate ajunge sub nici o forma in intersectia respectiva la momenul stabilit afisati -1 pe testul respectiv.
Restrictii
- Initial Ion se afla in intersectia 1 la momentul 0.
- Timpii la care se petrec infractiunile si la care Ion se poate intalni cu sotia sa sunt in intervalul [0, 1000]
- 0 ≤ K ≤ 1000
- 1 ≤ N ≤ 100
- 1 ≤ M ≤ 1000
- Costul unei amenzi va fi un intreg din intervalul [1, 1000]
Exemplu
| amenzi.in | amenzi.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
