大牛们求教_第三个点没有过是为什么?

编译通过... 

├ 测试数据 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 条评论

  • @ 2017-07-25 21:23:22

    第三个点的负权回路与源点不在同一个连通分量内

  • 1

信息

ID
1053
难度
8
分类
图结构 | 最短路 点击显示
标签
(无)
递交数
7499
已通过
674
通过率
9%
被复制
9
上传者