PWRFAIL - Mất điện
Tác giả: flashmt
Ngôn ngữ: Pascal
uses math;
const fi='';
oo=1000000;
var n,m,xx,yy,i,j,k:longint;
a:array[1..1000,1..1000] of boolean;
x,y:array[1..1000] of longint;
d:array[1..1000] of real;
free:array[1..1000] of boolean;
z,zz,mn:real;
function calc(u,v:longint):real;
var t,tt:real;
begin
t:=x[u]-x[v]; tt:=y[u]-y[v];
calc:=sqrt(t*t+tt*tt);
end;
begin
assign(input,fi); reset(input);
read(n,m,z);
for i:=1 to n do read(x[i],y[i]);
for i:=1 to m do
begin
read(xx,yy);
a[xx,yy]:=true; a[yy,xx]:=true;
end;
for i:=1 to n do
begin
free[i]:=true;
d[i]:=oo;
end;
free[1]:=false; d[1]:=0; xx:=1;
repeat
for j:=1 to n do
if free[j] then
begin
if a[xx,j] then d[j]:=d[xx]
else
begin
zz:=calc(xx,j);
if zz<=z then d[j]:=min(d[j],d[xx]+zz);
end;
end;
k:=0; mn:=oo;
for j:=1 to n do
if free[j] and (d[j]<mn) then
begin
mn:=d[j]; k:=j;
end;
if k=0 then break;
xx:=k; free[xx]:=false;
until not free[n];
if free[n] then writeln(-1)
else writeln(trunc(d[n]*1000));
close(input);
end.