Fişierul intrare/ieşire:sistem3.in, sistem3.outSursăAlgoritmiada 2014, Runda 1
AutorAdrian VladuAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.5 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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.insistem3.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?