PWRFAIL - Mất điện

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
const
  FINP='';
  FOUT='';
  MAXN=1000;
  oo=1000000000;
var
  c:array[1..MAXN,1..MAXN] of double;
  d,x,y:array[1..MAXN] of double;
  h,hpos:array[1..MAXN] of longint;
  hsize,n:longint;
  l:double;
function dist(x1,y1,x2,y2:double):double;
begin
  dist:=sqrt(sqr(x1-x2)+sqr(y1-y2));
end;
procedure inp;
var
  f:text;
  i,j,u,v,m:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n,m,l);
  for i:=1 to n do read(f,x[i],y[i]);
  for i:=1 to n do
  for j:=1 to n do
    begin
      c[i,j]:=dist(x[i],y[i],x[j],y[j]);
      if c[i,j]>l then c[i,j]:=oo;
    end;
  for i:=1 to m do
    begin
      read(f,u,v);
      c[u,v]:=0;
      c[v,u]:=0;
    end;
  close(f);
end;
procedure ans;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  if d[n]=oo then writeln(f,-1)
  else writeln(f,trunc(d[n]*1000));
  close(f);
end;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure downHeap(i:longint);
var
  j:longint;
begin
  j:=i shl 1;
  while (j<=hsize) do
    begin
      if (j<hsize) and (d[h[j+1]]<d[h[j]]) then inc(j);
      if (d[h[j]]<d[h[i]]) then
        begin
          swap(hpos[h[i]],hpos[h[j]]);
          swap(h[i],h[j]);
        end;
      i:=j; j:=i shl 1;
    end;
end;
procedure upHeap(i:longint);
var
  j:longint;
begin
  j:=i shr 1;
  while (i>1) and (d[h[i]]<d[h[j]]) do
    begin
      swap(hpos[h[i]],hpos[h[j]]);
      swap(h[i],h[j]);
      i:=j; j:=i shr 1;
    end;
end;
procedure push(u:longint);
begin
  inc(hsize); hpos[u]:=hsize; h[hsize]:=u;
  upHeap(hsize);
end;
procedure pop(var u:longint);
begin
  u:=h[1]; hpos[u]:=0;
  swap(h[1],h[hsize]);
  hpos[h[1]]:=1;
  dec(hsize); downHeap(1);
end;
procedure solve;
var
  u,v:longint;
begin
  for u:=1 to n do d[u]:=oo;
  d[1]:=0; push(1);
  while hsize>0 do
    begin
      pop(u);
      if u=n then exit;
      for v:=1 to n do
      if d[v]>d[u]+c[u,v] then
        begin
          d[v]:=d[u]+c[u,v];
          if hpos[v]=0 then push(v)
          else upHeap(hpos[v]);
        end;
    end;
end;
begin
  inp;
  solve;
  ans;
end.

Download