5 条评论
-
乖孩子 LV 3 @ 2014-10-29 18:36:28
百度呗
-
@ 2014-08-06 18:16:11
orz
-
@ 2014-08-05 19:38:58
Orz
-
@ 2014-08-05 19:15:31
蒟蒻乱打的
-
@ 2014-08-05 19:15:22
var
graph:array[1..100,1..100]of longint;
n,m:longint;
dist:array[1..100]of longint;
procedure init;
var
i,j,a,b:longint;
begin
read(n,m);
for i:=1 to m do
begin
read(a,b);
read(graph[a,b]);
end;
for i:=2 to n do
dist[i]:=maxlongint;
dist[1]:=0;
end;
procedure spfa;
var
q:array[1..100]of longint;
inq:array[1..100]of boolean;
front,tail,i,x:longint;
begin
fillchar(q,sizeof(q),0);
fillchar(inq,sizeof(inq),false);
front:=1;
tail:=1;
q[1]:=1;
while tail>=front do
begin
x:=q[front];
inc(front);
inq[x]:=false;
for i:=1 to n do
if (graph[x,i]>0)and(dist[i]>dist[x]+graph[x,i]) then
begin
dist[i]:=dist[x]+graph[x,i];
if not inq[i] then
begin
inq[i]:=true;
inc(tail);
q[tail]:=i;
end;
end;
end;
end;
procedure print;
var
i:longint;
begin
for i:=2 to n do
write(dist[i],' ');
end;
begin
init;
spfa;
print;
end.
- 1
