steinsgate

Steins;Gate

== include(page="template/taskheader" task_id="steinsgate") ==

Poveste şi cerinţă...

Okabe are de descifrat un nou mister. Pentru a realiza acest lucru, el trebuie sa afle riscul de a forma un paradox in fiecare linie a timpului in care acesta se afla.
 
Mai exact, fie un graf cu $N$ noduri si $M$ muchii ORIENTATE (nodurile reprezinta stari in timp si muchiile relatii intre aceste stari, fapt irelevant). Pentru fiecare nod $X$ se cunoaste o valoare $risc[X]$ la evenimentul $0$. Dupa fiecare eveniment nou, riscul dintr-un nod $X$ se propaga in toti vecinii acestuia (daca exista muchie de la $X$ la $Y$). Deoarece universul este complicat, riscul unui nod devine dupa fiecare eveniment, maximul valorilor care se propaga in acest nod. Misiunea lui Okabe este sa afle riscul din fiecare nod dupa $K$ evenimente.

h2. Date de intrare

Fişierul de intrare $steinsgate.in$ ...

Fişierul de intrare $steinsgate.in$ va contine pe prima linie $3$ numere naturale $N$, $M$ si $K$. Pe urmatoarele $M$ linii se afla cate $2$ numere naturale $X$ si $Y$ reprezentand faptul ca avem muchie de la $X$ la $Y$. Pe ultima linie vor fi $N$ numere naturale, elementul al $i$-lea reprezentand riscul nodului $i$ la evenimentul $0$.

h2. Date de ieşire

În fişierul de ieşire $steinsgate.out$ ...

Fişierul de ieşire $steinsgate.out$ va contine o singura linie cu $N$ numere naturale reprezentand riscul fiecarui nod dupa $K$ evenimente.

h2. Restricţii

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

* $1 ≤ N ≤ 200$
* $1 ≤ M ≤ N * N$
* $1 ≤ K ≤ 1.000.000.000$
* $1 ≤ risc[i] ≤ 1.000.000.000$
* Se garanteaza ca pentru fiecare nod $X$, exista cel putin un nod $Y$ astfel incat sa avem muchie de la $Y$ la $X$ (exista cel putin un nod $Y$ care isi propaga riscul in $X$)
* Pentru teste in valoare de *30* de puncte $K ≤ 100.000$

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

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

|5 6 3
1 2
2 3
3 4
4 5
5 1
1 4
7 3 9 1 4
|9 1 4 7 4

|

h3. Explicaţie
 
...
 

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