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