Fişierul intrare/ieşire:steinsgate.in, steinsgate.outSursăAlgoritmiada 2016 - Runda 2, Seniori
AutorEugenie Daniel PosdarascuAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test2.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Steins;Gate

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.

Date de intrare

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.

Date de ieşire

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

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

Exemplu

steinsgate.insteinsgate.out
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?