spfa+前向星
超时。。。。。。why
大神求助啊
var
i,j,n,m,head,tail,x,y:longint;
s,t:int64;
q:array[0..1000000]of longint;
a,b,c,d,f:array[0..100000]of longint;
w:array[0..100000]of boolean;
procedure kuai(x,y:longint);
var
i,j,l,t:longint;
begin
i:=x;
j:=y;
l:=a[(x+y)div 2];
repeat
while (a[i]<l) do i:=i+1;
while (a[j]>l) do j:=j-1;
if i<=j then
begin
t:=a[i];a[i]:=a[j];a[j]:=t;
t:=b[i];b[i]:=b[j];b[j]:=t;
t:=c[i];c[i]:=c[j];c[j]:=t;
i:=i+1;
j:=j-1;
end;
until i>j ;
if i<y then kuai(i,y);
if j>x then kuai(x,j);
end;
////////////////////////////////////////////////////////////////////////////
procedure inte;
begin
readln(n,m,t);
for i:=1 to m do
begin
readln(a[i],b[i],c[i]);
a[i+m]:=b[i];b[i+m]:=a[i];c[i+m]:=c[i];
end;
m:=m*2;
kuai(1,m);
for i:=1 to m do
if f[a[i]]=0 then
f[a[i]]:=i;
f[n+1]:=m+1;
for i:=1 to n do
d[i]:=1000000;
end;
procedure spfa;
begin
d[1]:=0;
head:=1;
tail:=1;
q[1]:=1;
fillchar(w,sizeof(w),false);
w[1]:=true;
while head<=tail do
begin
x:=q[head];
for i:=f[x] to f[x+1]-1 do
if c[i]+d[x]<d[b[i]] then
begin
d[b[i]]:=c[i]+d[x];
if w[b[i]]=false then
begin
w[b[i]]:=true;
inc(tail);
q[tail]:=b[i];
end;
end;
w[x]:=false;
head:=head+1;
end;
end;
///////////////////////////////////////////////////////////////
procedure print;
begin
s:=0;
for i:=2 to n do
s:=s+d[i]*2;
writeln(s);
if s>t then writeln('escape')
else writeln('run');
end;
///////////////////////////////////////////////////////////////
begin
inte;
spfa;
print;
end.