Fişierul intrare/ieşire:cameras.in, cameras.outSursăACM-ICPC Faza Nationala 2018
AutorMihai CalanceaAdăugată de
Timp execuţie pe test1 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultateN/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. Dacă o maşină a ajuns din nodul ni în nodul ni + 1 într-un timp mai mic decât timpul în care se poate ajunge din ni în $ni + 1 pe drumul cel mai scurt şi cu viteza LIMIT, atunci sistemul îşi dă seama că maşina respectivă a întrecut limita de viteză. 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.incameras.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?