讨论 / 求教
451060344 2013-10-24 22:37:00
点我顶贴 收藏 删除
var path:array[-10..18000,-10..18000] of longint;

dist:array[-10..30010] of longint;

q:array[-10..150010] of longint;

flag:array[-10..30010] of boolean;

n,m,a,b,w,i:longint;

procedure init;

begin

fillchar(dist,sizeof(dist),127);

fillchar(path,sizeof(path),0);

fillchar(flag,sizeof(flag),false);

fillchar(q,sizeof(q),0);

readln(n,m);

for i:=1 to m do

begin

readln(a,b,w);

path[a,b]:=w;

path[b,a]:=w;

end;

dist[1]:=0;

end;

function relax(u,v:longint):boolean;

begin

if (path[u,v]<>0) and (dist[u]+path[u,v]<dist[v]) then

begin

dist[v]:=dist[u]+path[u,v];

exit(true);

end

else exit(false);

end;

procedure spfa(s:longint);

var h,t,v:longint;

begin

h:=0;t:=0;

inc(t);q[t]:=s;flag[s]:=true;

while h<>t do

begin

h:=(h mod n)+1;

v:=q[h];

flag[v]:=false;

for i:=1 to n do

if relax(v,i) then

if not flag[i] then

begin

t:=(t mod n)+1;

q[t]:=i;

flag[i]:=true;

end;

end;

end;

begin

init;

spfa(1);

writeln(dist[n]);

end.

#1 451060344@2013-10-24 22:37:00
回复 删除
补充

341 星门跳跃

求大神

查看更多回复
提交回复