Diferențe pentru problema/risipa între reviziile #4 si #2

h2. Restricții

* $1 ≤ n ≤ 100.000$
* $1 ≤ m ≤ 300.000$
* $1 ≤ h, u, v ≤ n$
* $1 ≤ c[~i~] ≤ 10.000$ pentru orice $1 ≤ i ≤ n$
* Nu există străzi de la o intersecție la ea însăși.
* Între orice intersecții $u$ și $v$ ($u ≠ v$) există cel mult o stradă în fiecare sens.
 
table{width: inherit}.
|_. subtask |_. puncte |_. restricții |
| 1 | 20 | $n ≤ 1.000$; $m ≤ 10.000$; harta este aciclică. |
| 2 | 20 | $n ≤ 1.000$; $m ≤ 10.000$ |
| 3 | 28 | Harta este aciclică. |
| 4 | 32 | Fără restricții suplimentare. |

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example).
|_. risipa.in |_. risipa.out |

| 7 8 1
5 3 2 3 4 1 4
4 2
4 6
1 7
2 3
3 7
1 2
3 4
5 4
| 5
13
13
13
0
14
17

| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.

|
h3. Explicație

Datele corespund acestei hărți:
 
!problema/risipa?risipa-graph.svg!
 
* Pentru a ajunge în intersecția 1, Maria nu poate vizita decît magazinul 1. Dacă părăsește intersecția, nu mai poate reveni pentru cină.
* Pentru a ajunge în intersecțiile 2, 3 sau 4, Maria poate vizita intersecțiile 1, 2, 3 și 4.
* Maria nu poate ajunge în intersecția 5.
* Pentru a ajunge în intersecția 6, Maria poate vizita intersecțiile 1, 2, 3, 4 și 6.
* Pentru a ajunge în intersecția 7, Maria poate vizita intersecțiile 1, 2, 3, 4 și 7. Ea nu va merge direct pe strada 1-7, căci ar cheltui mai puțin astfel.

...

== include(page="template/taskfooter" task_id="risipa") ==