Fişierul intrare/ieşire:dbz.in, dbz.outSursăLot Mehedinți 2015 - Baraj 6 Seniori
AutorMihai CiucuAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test2.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Dragon Ball Z

Goku a ajuns în viaţa de apoi, să se antreneze pentru lupta finală cu Majin Boo. El vrea să se antreneze pe cele N planete cu Kai, şi ştie în cât timp se poate deplasa între anumite perechi de planete (doar între perechile date se poate deplasa). Pentru fiecare planetă pe care ar putea să se afle, vă roagă să îi spuneţi care este drumul de durata minimă care ar pleca din acea planetă şi care s-ar întoarce tot acolo, folosind un drum care leagă direct două planete maxim o singură dată. El l-a întrebat pe vărul său, Goku Marian, însa acesta nu se prea descurcă şi are nevoie de ajutorul vostru.

Date de intrare

Pe prima linie a fişierului de intrare dbz.in se vor afla numerele naturale N şi M. Pe următoarele M linii vor fi trei numere x, y şi z, reprezentând faptul că există drum bidirecţional între planetele x şi y cu durată de deplasare z.

Date de ieşire

În fişierul de ieşire dbz.out se va afişa, pentru fiecare planetă de la 1 la N, durata minimă a unui drum care porneşte de pe acea planetă şi se termină tot pe ea, folosind un drum care leagă direct două planete maxim o singură dată. În cazul în care nu există un asemenea drum, afişaţi numărul -1 pentru acea planetă.

Restricţii

  • 1 ≤ N ≤ 1 500
  • 1 ≤ M ≤ 30 000
  • 1 ≤ durata fiecărei deplasări z ≤ 9 000 (nu este over 9000!)
  • Pentru fiecare pereche de planete (x, y) există maxim un drum direct între ele.

Exemplu

dbz.indbz.out
5 6
1 2 1
1 4 2
4 3 4
2 3 2
4 5 3
3 5 6
9 9 9 9 13
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?