Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | cameras.in, cameras.out | Sursă | ACM-ICPC Faza Nationala 2018 |
| Autor | Mihai Calancea | Adăugată de | |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 32768 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cameras
Ai intrat cu maşina într-un graf orientat G cu costuri pe muchii. Costul unei muchii denotă lungimea acesteia în kilometri. Momentan te afli în nodul 1 şi vrei să ajungi în nodul N cât mai repede. Maşina ta are o viteză maximă egală cu Vmax km/h. Există o limită superioară de viteză în graf, egală cu LIMIT km/h. Pentru a verifica respectarea acestei limite, administratorii grafului au plasat camere speciale de trafic în K dintre cele N noduri. Ele funcţionează astfel:
- Pentru fiecare nod care conţine o cameră, camera va înregistra toate maşinile care intră în respectivul nod sau care îl părăsesc şi va consemna momentele de timp la care au loc aceste evenimente.
- Dacă o maşină trece prin mai multe noduri cu cameră, fie ele, în ordine, n1, n2 .. nk, atunci sistemul poate verifica pentru fiecare pereche ni, ni + 1 dacă maşina respectivă a întrecut limita de viteză în segmentul de drum de la ni la ni + 1. Notaţi că nu este necesar ca nodurile speciale din acest şir să fie singurele noduri din drumul parcurs de maşină. Pot exista oricâte noduri fără camera pe segmentul de drum dintre ni si ni + 1.
Se cere să se afle timpul minim în care se poţi ajunge din nodul 1 în nodul N fără a fi prins de sistem că ai încălcat limita de viteză.
Date de intrare
Pe prima linie a fişierului de intrare se află numerele N, M şi K, reprezentând numărul nodurilor, numărul muchiilor grafului şi numărul oraşelor în care există o cameră.
A doua linie a fişierului de intrare conţine cele K oraşe în care se află o cameră.
Pe următoarea linie se află valorile Vmax şi LIMIT.
Pe următoarele M linii se află câte o muchie în forma from to length, însemnând că există o muchie unidirecţională de la nodul from la nodul to de lungime length km.
Date de ieşire
Pe unica linie a fişierului de ieşire trebuie să se afle timpul minim în care maşina poate ajunge din nodul 1 în nodul N fără ca sistemul să observe că a întrecut limita de viteză.
Restricţii
- 2 ≤ N ≤ 100.000
- 1 ≤ M ≤ 250.000
- 1 ≤ K ≤ N
- 1 ≤ Vmax, LIMIT, length ≤ 30.000, unde length reprezintă lungimea unei muchii. Toate aceste valori sunt numere întregi.
- Se garantează că există cel puţin un drum de la nodul 1 la nodul N.
- Răspunsul dat poate să difere de cel real prin cel mult 10-9
Exemplu
| cameras.in | cameras.out |
|---|---|
| 4 7 3 2 3 4 10 5 1 2 1 2 4 5 4 1 1 3 2 9 2 3 3 4 3 10 3 4 4 | 1.100000 |
