Fişierul intrare/ieşire:razbunare.in, razbunare.outSursăLot 2017 Baraj 3
AutorRazvan SalajanAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.8 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/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 * 104
  • 1 ≤ Q ≤ 3 * 105
  • 0 ≤ c (costul unei muchii), r (costul de refuz) ≤ 104
  • 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

razbunare.inrazbunare.outExplicaţie
5 5 3
1 4 4 5
4 1 6 1
2 1 2 9
2 5 1 0
1 5 2 5
2 2 2 4
5 4 5 5
1 5 2 5
10
-1
9
Pentru prima misiune: Gigel se află în nodul 2 şi vrea să ajungă tot în nodul 2. Costul minim de a ajunge din 2 în 2 e să refuze toate muchiile din [2, 4]: 1 + 9 + 0 (astfel rămâne tot timpul în nodul 2).
Pentru a 2-a misiune: Gigel nu poate ajunge din 5 în 4
Pentru a 3-a misiune: Gigel se află iniţial în 1 şi foloseşte muchiile din [2,5]. Refuză a doua muchie (4,1); alege a treia muchie si ajunge în 2; alege a patra muchie si ajunge în 5 si refuză a cincea muchie: 1 + 2 + 1 + 5.
4 8 6
2 4 5 8
2 4 4 8
2 3 6 4
1 4 5 0
2 4 10 10
1 3 5 2
3 2 2 9
3 4 1 1
3 2 1 5
3 1 2 2
1 1 1 7
2 3 2 4
3 3 1 7
1 2 2 5
32
-1
41
14
36
27
...
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?