== include(page="template/taskheader" task_id="risipa") ==
Poveste și cerință...
Ion și Maria merg în concediu la Paris. Parisul constă din $n$ intersecții conectate prin $m$ străzi cu sens unic. La fiecare intersecție $i$ ($1 ≤ i ≤ n$) se află un magazin de suveniruri cu marfă în valoare de $c[~i~]$. Ion și Maria se cazează la un hotel din intersecția $h$.
Dimineața, Maria spune: „Ioane, eu mă duc la muzee. Spune-mi unde ieșim la cină și ne vedem acolo!”. Ion este îngrozit, pentru că știe ce înseamnă asta. Dacă alege pentru cină o intersecție $i$ inaccesibilă de la hotel, atunci Maria va sta în cameră supărată. În schimb, dacă intersecția $i$ este accesibilă, atunci Maria, pornind de la hotel, va colinda pe toate străzile, intrînd în toate magazinele de suveniruri pe care le întîlnește și cumpărînd toată marfa. Poate chiar să viziteze unele străzi și intersecții de mai multe ori (dar magazinele nu mai aduc altă marfă în afară de cea inițială). Maria va cheltui cît mai mult posibil, iar seara va veni la întîlnire.
Ion vă cere ajutorul. Pentru fiecare intersecție, aflați suma pe care o va cheltui Maria dacă Ion îi propune să se întîlnească în acea intersecție.
h2. Date de intrare
Fișierul de intrare $risipa.in$ ...
Fișierul de intrare $risipa.in$ conține pe prima linie numerele $n$, $m$ și $h$. Următoarea linie conține valorile $c[~1~] c[~2~] ... c[~n~]$. Următoarele $m$ linii conțin perechi $u v$ cu semnificația că există o stradă cu sensul de la $u$ spre $v$.
h2. Date de ieșire
În fișierul de ieșire $risipa.out$ ...
În fișierul de ieșire $risipa.out$ afișați, pentru fiecare intersecție $i$ ($1 ≤ i ≤ n$), pe cîte o linie separată, suma pe care o va cheltui Maria dacă cina este într-un restaurant din intersecția $i$. Dacă nu există niciun drum de la hotel la intersecția $i$, afișați 0.
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).
table(example).
|_. risipa.in |_. risipa.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
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") ==
