Fişierul intrare/ieşire:avioane2.in, avioane2.outSursăONIS 2016 Runda Online
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Avioane2

Mihai si Alexandra s-au decis sa mearga in vacanta in strainatate. Problema lui Mihai este ca mereu Alexandra trebuie sa decida daca are rost sa mearga intr-o anumita excursie sau nu (in functie de bani, timp, etc.).

Fie N aeroporturi (reprezentate ca nodurile unui graf) si M zboruri (muchiile grafului). Pentru fiecare zbor se cunoaste indicele aeroportului si timpul la care decoleaza avionul, indicele aeroportului si timpul la care aterizeaza avionul si pretul biletului pentru acest zbor. Mihai si Alexandra se afla in aeroportul 1 la timpul 0. Mihai trebuie sa raspunda la K query-uri de tipul (x,y): care este pretul minim pentru a ajunge in aeroportul x la timpul maxim y.

Date de intrare

Fişierul de intrare avioane2.in va contine pe prima linie 3 numere naturale N, M si K. Pe urmatoarele M linii se afla cate 5 valori reprezentand detaliile unui zbor: A, Tdec, B, TAter (avionul pleaca din A la timpul Tdec si ajunge in B la timpul TAter) si P, pretul biletului. Urmatoarele K linii contin cate 2 numere naturale reprezentand query-urile de tipul (x,y).

Date de ieşire

Fişierul de ieşire avione.out va contine K linii, rasunsul pentru fiecare query. Daca nu se poate ajunge intr-un anumit pana la un anumit timp dat, afisati -1.

Restricţii

  • 1 ≤ N ≤ 30.000
  • 1 ≤ M ≤ 90.000
  • 1 ≤ K ≤ 120.000
  • Toate celalalte valori fac parte din intervalul [1, 109]
  • Mihai si Alexandra trebuie sa plateasca un singur bilet pentru fiecare zbor.
  • Personajele pot astepta oricat intr-un aeroport (la o cafea) urmatorul zbor.
  • Tdec < TAter pentru fiecare din cele M zboruri

Exemplu

avioane2.inavioane2.out
5 7 6
1 4 5 8 69
2 14 3 17 25
4 2 5 10 564
5 8 2 13 12
3 20 1 25 54
2 4 4 7 34
1 1 3 8 1000
3 10
3 20
5 7
2 20
1 100
5 13
1000
106
-1
81
0
69
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?