Question

Problema 1887 de pe pbinfo

Cerința
Dijkstra este un cetățean model al comunității în care trăiește. El își ajută fiecare vecin aflat în necaz. Astăzi, Vlad îi cere ajutorul și îl roagă să livreze câte un pachet fiecărui vecin de-al lor. Știind că sunt n case în aceasta comunitate, iar distanțele dintre ele variază, Dijkstra vă roagă să realizați un program care să afișeze costul drumului minim dintre casa p, casa lui Vlad, și casele vecinilor. În cazul în care nu există drum până la unul dintre vecini, se va afișa -1.

Date de intrare
Programul citește din fișier numărul n, numărul de case din comunitate, m, numărul de drumuri dintre case, p, numărul casei lui Vlad, iar pe următoarele m linii se vor afla x, y și d cu semnificația că există drum între casele x și y de lungime d.

Date de ieșire
Programul va afișa n numere separate printr-un spațiu, al i-lea număr reprezentând distanța minimă de la casa lui Vlad la casa i.

Restricții și precizări
1 ≤ p ≤ n ≤ 100.000
1 ≤ m ≤ 250.000
cele m distanțe citite vor fi mai mici decât 20.000

Exemplu
dijkstra2.in

5 6 2
3 5 1
5 4 9
4 3 5
1 2 2
3 2 2
1 3 8
dijkstra2.out

2 0 2 7 3
Explicație
Drumurile minime de la casa lui Vlad la celelalte case sunt 2 0 2 7 3.

Am nevoie de un cod de 100 de pcte, caci nu inteleg de ce codului meu imi da 30 pcte, pe cand pe infoarena la o problema similara da 100.

Answer 1

Ti-am atasat solutia in C++. Succes!

87d1a1f1cfe2c113e5c46455c949fda6.cpp