RE好多。。

P1462 通往奥格瑞玛的道路

pupuvovovovovo @ 2016-07-25 21:26:24

var first,last,fc,f:array [1..10000] of int64;
next,en,blod,fee:array [1..50000] of int64;
dl:array [1..100000] of longint;
b:array [1..10000] of boolean;
h,t,l,r,mid,ans,n,m,blood,x,y,z,top,ma,mi:int64;
i:longint;
flag:boolean;
function max(a,b:longint):longint;
begin
  if a>b then exit(a);
  exit(b);
end;
procedure add(x,y,z:longint);
begin
  inc(top);
  if first[x]=0 then first[x]:=top
  else next[last[x]]:=top;
  last[x]:=top;
  en[top]:=y;
  blod[top]:=z;
  fee[top]:=max(fc[x],fc[y]);
end;
function judge(x:longint):boolean;
var i:longint;
begin
  fillchar(f,sizeof(f),127);
  fillchar(dl,sizeof(dl),0);
  fillchar(b,sizeof(b),true);
  f[1]:=0;
  h:=0;
  t:=1;
  dl[1]:=1;
  repeat
    inc(h);
    b[dl[h]]:=true;
    i:=first[dl[h]];
    while i>0 do
    begin
      if (f[en[i]]>f[dl[h]]+blod[i]) and (fee[i]<=x) then
      begin
        f[en[i]]:=f[dl[h]]+blod[i];
        if b[en[i]] then
        begin
          b[en[i]]:=false;
          inc(t);
          dl[t]:=en[i];
        end;
      end;
      i:=next[i];
    end;
  until h=t;
  if f[n]<=blood then exit(true);
  exit(false);
end;
begin
  mi:=maxlongint;
  read(n,m,blood);
  for i:=1 to n do
  begin
    read(fc[i]);
    if fc[i]>ma then ma:=fc[i];
    if fc[i]<mi then mi:=fc[i];
  end;
  for i:=1 to m do
  begin
    read(x,y,z);
    add(x,y,z);
    add(y,x,z);
  end;
  l:=mi;
  r:=ma;
  while l<=r do
  begin
    mid:=(l+r) div 2;
    if judge(mid) then
    begin
      flag:=true;
      ans:=mid;
      r:=mid-1;
    end
    else l:=mid+1;
  end;
  if not(flag) then write('AFK')
  else write(ans);
end.

为甚么7-8个点运行时错误? longint与int64改了好多遍了。


by pupuvovovovovo @ 2016-07-27 11:59:12

貌似这题给的数据范围有问题问题问题问题问题问题问题!!!!!

存点与边10000与50000就RE!!


by zx2003 @ 2016-09-13 22:51:10

你边要存两遍吗?50000*2=100000


|