Fişierul intrare/ieşire:	razbunare.in, razbunare.out	Sursă	Lot 2017 Baraj 3
Autor	Razvan Salajan	Adăugată de	Eugenie Daniel Posdarascu •eudanip
Timp execuţie pe test	0.8 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Razbunare

Gigel are un graf neorientat G cu N noduri şi M muchii etichetate cu costuri pozitive. După încurcătura făcută de Gigel la Olimpiada Naţională de Informatică, Ninel, fratele mai mic al lui Gigel, i-a furat toate muchiile. Gigel doreşte să recupereze muchiile, dar Ninel îl pune la grele încercări.

Fie S un şir de lungime L ce conţine pe fiecare poziţie o muchie neorientată cu un cost asociat şi un cost r de refuz. Gigel are de îndeplinit următoarea misiune primită de la Ninel: trebuie să afle costul minim pentru a se deplasa din nodul u (din graful G) în nodul v (din graful G) folosindu-se de o secvenţă de muchii din şirul S. Acesta are la dispoziţie un interval [a, b] (cu a ≤ b) care determină ce muchii din şirul S are voie să folosească. Astfel Gigel se află iniţial în nodul u şi parcurge muchiile cu poziţiile corespunzătoare din [a, b] de la stânga la dreapta. La fiecare pas Gigel:

• fie alege să folosească muchia curentă dacă se afla în nodul x ajungând astfel în nodul y (respectiv dacă se afla în nodul y ajungând în nodul x); costul creşte cu costul asociat muchiei de la pasul curent
• fie refuză muchia curentă şi rămâne în nodul în care se afla în momentul când a ajuns la pasul curent; costul creşte cu costul de refuz asociat elementului din pasul curent

Se ştie numărul N de noduri, şirul S de muchii şi Q numărul de misiuni primite de Gigel. Şirul S conţine pe fiecare poziţie un tuplu de forma:

• <x, y, c, r> : c - reprezintă costul muchiei cu capetele în x şi y; r - reprezintă costul de refuz al muchiei curente
  Cele Q misiuni sunt de forma:
• <u, v, a, b> : Gigel se află iniţial în nodul u şi vrea să ajungă în nodul v. Acesta începe să parcurgă muchiile din intervalul [a, b] de la stânga la dreapta, la fiecare pas, alegând muchia sau refuzând-o.
  Se cere să se afle costul minim pentru fiecare din cele Q misiuni. În cazul în care Gigel nu poate ajunge din nodul u în nodul v, se afişează -1.

Date de intrare

Fişierul razbunare.in conţine pe prima linie N, numărul de noduri din graful G, urmat de L, lungimea şirului S, urmat de Q care reprezintă numărul de misiuni pe care Gigel trebuie să le facă. Pe următoarele S linii se află un tuplu de forma <x, y, c, r> cu semnificaţiile enunţate mai sus reprezetând muchiile din şirul S. Pe următoarele Q linii se află un tuplu de forma <u, v, a, b> reprezentând misiunile pe care trebuie să le facă Gigel.

Date de ieşire

Fişierul razbunare.out conţine Q numere reprezentând răspunsurile misiunilor primite de Gigel în ordinea din fişierul de intrare.

Restricţii

• 2 ≤ N ≤ 30
• 1 ≤ L ≤ 3 * 10⁴
• 1 ≤ Q ≤ 3 * 10⁵
• 0 ≤ c (costul unei muchii), r (costul de refuz) ≤ 10⁴
• 1 ≤ x, y, u, v ≤ N
• Pentru 10 puncte N ≤ 7, L ≤ 200, Q ≤ 200
• Pentru alte 30 puncte N ≤ 7, L ≤ 20.000, Q ≤ 20.000
• Pentru alte 10 puncte N ≤ 10, L ≤ 20.000, Q ≤ 60.000
• Pentru alte 25 de puncte N ≤ 22, L ≤ 20.000, Q ≤ 60.000
• Pentru alte 15 puncte N ≤ 30, L ≤ 25.000, Q ≤ 150.000
• Pentru restul de 10 puncte: restricţiile originale
• Pentru fiecare muchie din şirul S avem x ≠ y
• Nodurile sunt indexate de la 1 la N
• Şirul este indexat de la 1
• În cazul în care Gigel nu poate ajunge din nodul u în nodul v se afişează -1
• După ce Gigel a parcurs toate muchiile din interval, trebuie să se afle în nodul v
• Daca la un pas e imposibila folosirea unei muchii atunci Gigel e obligat sa o refuze.

Exemplu

Cum se trimit solutii?