| Fişierul intrare/ieşire: | sistem3.in, sistem3.out | Sursă | Algoritmiada 2014, Runda 1 |
| Autor | Adrian Vladu | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sistem3
Se da un graf G neorientat si conex cu N noduri si N muchii. Fiecare nod din acest graf are asociata o valoare numita potential. Potentialul nodului i este p[i]. De asemenea fiecare muchie a grafului are asociat un cost.
Definim gradientul unui nod i suma (p[j] - p[i]) * w[j][i] modulo M (M dat) unde j este vecin de-al lui i, iar w[j][i] este costul muchiei dintre i si j.
Din pacate potentialele nodurilor au fost pierdute. Se cunosc insa gradientele pentru fiecare nod si costurile de pe muchii. Vi se cere sa reconstituiti potentialele nodurilor stiind ca ele aveau valori cuprinse intre 0 si M - 1.
Date de intrare
Fişierul de intrare sistem3.in va contine pe prima linie doua numere naturale N si M reprezentand numarul de noduri (si muchii) din graf, respectiv valoarea fata de care se face modulo.
Urmatoarele N randuri vor contine fiecare cate 3 numere naturale x, y si w cu semnificatia: exista o muchie intre nodul x si nodul y de cost w.
Ultima linie va contine N numere naturale, a i-a valoare reprezentand gradientul nodului i.
Date de ieşire
În fişierul de ieşire sistem3.out trebuie sa se gaseasca N linii fiecare continand o valoare naturala intre 0 si M - 1, acestea reprezentand in ordine potentialele nodurilor 1, 2, .., N.
Restricţii
- 1 ≤ N ≤ 100.000
- 1 ≤ x, y ≤ N
- 1 ≤ w ≤ M - 1
- 2 ≤ M ≤ 46000
- M e prim
- 0 ≤ gradientul oricarui nod ≤ M - 1
- Pentru 30% din teste N <= 100
- Pentru 50% din teste una din muchii este de forma x x w
Exemplu
| sistem3.in | sistem3.out |
|---|---|
| 4 2 4 2 1 2 2 1 1 4 1 1 3 1 1 0 1 0 | 0 0 1 0 |
| 5 5 2 4 4 3 5 4 3 1 3 4 1 4 1 5 4 4 1 2 2 1 | 0 4 4 3 0 |
