ŠIOM — Dijkstros algoritmas

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Dijkstros algoritmas

Duotas orientuotas svorinis grafas, kurį sudaro $n$ viršūnių ir $m$ briaunų. Raskite trumpiausius atstumus nuo $1$ -osios viršūnės iki visų kitų. Laikykite, kad iš $1$ -osios viršūnės galima pasiekti visas kitas.

Pradiniai duomenys

Pirmojoje eilutėje pateikti du skaičiai $n$ ( $1\\leqn\\leq10^5)$ ir $m$ ( $1\\leqm\\leq2\\times10^5$ ). Tolesnėse $m$ eilučių pateikti trys skaičiai $a_i$ , $b_i$ ir $w_i$ ( $1\\lea_i,b_i\\len$ , $1\\lew_i\\le10^9$ ), reiškiantys, jog tarp $a_i$ -osios viršūnės ir $b_i$ -osios yra kryptinė briauna (briaunos kryptis - iš $a_i$ į $b_i$ ), kurios svoris $w_i$ .

Rezultatai

Išveskite tarpais atskirtus $n$ skaičių: trumpiausius atstumus nuo $1$ -osios viršūnės iki visų kitų.

Pavyzdys

Duomenys	Rezultatai
3 4 1 2 6 1 3 2 3 2 3 1 3 4	0 5 2

Šeštadieninė informatikos olimpiadininkų mokykla

Dijkstros algoritmas

Pradiniai duomenys

Rezultatai

Pavyzdys