Pagini recente » Cod sursa (job #1665782) | Cod sursa (job #2753829) | Cod sursa (job #2555195) | Cod sursa (job #882654) | Cod sursa (job #1430663)
program asdf;
const Maxnod = 50005;
Maxmuchii = 250005;
var f, g:text;
n, m, k, i, j, cost, p, u, z, nod:longint;
t:array[0..2, 1..Maxmuchii] of longint;
start, d:array[1..maxnod] of longint;
coada:array[1..10*maxnod] of longint;
viz:array[1..maxnod] of boolean;
begin
assign(f, 'dijkstra.in'); reset(f);
assign(g, 'dijkstra.out'); rewrite(g);
readln(f, n, m);
for k := 1 to m do
begin
readln(f, i, j, cost);
t[0, k] := j;
t[1, k] := start[i];
start[i] := k;
t[2, k] := cost;
end;
for i := 2 to n do d[i] := maxlongint;
d[1] := 0;
p := 1; u := 1;
coada[1] := 1;
while p <= u do
begin
nod := coada[p];
viz[nod] := false;
z := start[nod];
while z <> 0 do
begin
if d[nod] + t[2, z] < d[t[0, z]] then
begin
d[t[0, z]] := d[nod] + t[2, z];
if not viz[t[0, z]] then
begin
inc(u);
coada[u] := t[0, z];
viz[t[0, z]] := true;
end;
end;
z := t[1, z];
end;
inc(p);
end;
for i := 2 to n do
if d[i] = maxlongint then write(g,'0 ')
else write(g, d[i],' ');
close(f); close(g);
end.