== include(page="template/taskheader" task_id="razbunare") ==
Poveste şi cerinţă...
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$.
h2. Date de intrare
Fişierul de intrare $razbunare.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $razbunare.out$ ...
Fişierul $razbunare.out$ conţine $Q$ numere reprezentând răspunsurile misiunilor primite de Gigel în ordinea din fişierul de intrare.
h2. Restricţii
* $... ≤ ... ≤ ...$
h2. Exemplu
* $2 ≤ N ≤ 30$
* $1 ≤ L ≤ 3 * 10^4^$
* $1 ≤ Q ≤ 3 * 10^5^$
* $0 ≤ c$ (costul unei muchii), $r$ (costul de refuz) $≤ 10^4^$
* $1 ≤ x, y, u, v ≤ N$
* Pentru $10$ puncte $N ≤ 7, L ≤ 200, Q ≤ 200$
* Pentru alte $30$ puncte $N ≤ 7, L ≤ 20000, Q ≤ 20000$
* Pentru alte $10$ puncte $N ≤ 10, L ≤ 20000, Q ≤ 60000$
* Pentru alte $25$ de puncte $N ≤ 22, L ≤ 20000, Q ≤ 60000$
* Pentru alte $15$ puncte $N ≤ 30, L ≤ 25000, Q ≤ 150000$
* 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$
table(example). |_. razbunare.in |_. razbunare.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
h2. Exemplu
...
table(example). |_. razbunare.in |_. razbunare.out |_. Explicaţ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.$
|
|3 3
1 2 2
2 3 3
1 3 5
|10
|Putem alege pungile astfel:
Punga 1 va conţine tipurile 1, 3 şi va fi preparată la timpul 1.
Punga 2 va conţine tipul 2 şi va fi preparată la timpul 2.
Punga 3 va fi goală.
|
== include(page="template/taskfooter" task_id="razbunare") ==
