| Fişierul intrare/ieşire: | steinsgate.in, steinsgate.out | Sursă | Algoritmiada 2016 - Runda 2, Seniori |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 1.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | steinsgate.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 |
