- Easy sssp
- 2012-07-26 20:19:47 @
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案错误...程序输出比正确答案长
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
第三个点正解是-1,但我可能输出了d[i]数组,就是说没有判断出负权回路,难道有什么猫腻呢,第三个点?
var
i,j,n,m,s,tot,a,b,c:longint;
q:array[0..9999999] of longint;
v:array[0..555555] of boolean;
d,num:array[0..555555] of longint;
next,head,pb,pc:array[0..555555] of longint;
procedure Add(a,b,c:longint);
begin
inc(tot);next[tot]:=head[a];head[a]:=tot;pb[tot]:=b;pc[tot]:=c;
end;
procedure spfa;
var
i,j,h,t,x:longint;
begin
fillchar(v,sizeof(v),false);
fillchar(d,sizeof(d),0);
h:=0;t:=0;
for i:=1 to n do
begin
inc(t);
q[t]:=i;
end;
while ht do
begin
inc(h);
x:=q[h];
i:=head[x];
while i0 do
begin
if d[x]+pc[i]n then begin writeln(-1);close(output);halt;end;
q[t]:=pb[i];
end;
i:=next[i];
end;
end;
end;
procedure spfaa;
var
i,j,h,t,x:longint;
begin
fillchar(v,sizeof(v),false);
fillchar(d,sizeof(d),63);
h:=0;t:=1;q[1]:=s;v:=true;d:=0;
while ht do
begin
inc(h);
x:=q[h];
v[x]:=false;
i:=head[x];
while i0 do
begin
if d[x]+pc[i]1000000000 then writeln('NoPath') else writeln(d[i]);
close(input);close(output);
end.
1 条评论
-
wanghaozhou LV 8 @ 2017-07-25 21:23:22
第三个点的负权回路与源点不在同一个连通分量内
- 1