PWRFAIL - Mất điện
Tác giả: ll931110
Ngôn ngữ: Pascal
Program PWRFAIL;
Const
input = '';
output = '';
max = 50000000000000;
epsilon = 0.000000000001;
Var
x,y: array[1..1000] of longint;
c: array[1..1000,1..1000] of real;
d: array[1..1000] of real;
free: array[1..1000] of boolean;
n,w: longint;
m: real;
fi,fo: text;
Procedure init;
Var
i: longint;
Begin
Assign(fi, input);
Reset(fi);
Readln(fi, n, w);
Readln(fi, m);
For i:= 1 to n do readln(fi, x[i], y[i]);
End;
Procedure LoadGraph;
Var
a,b,k: real;
i,j,u,v: longint;
Begin
For i:= 1 to n do
For j:= 1 to n do
if i = j then c[i,j]:= 0 else c[i,j]:= max;
For i:= 1 to n - 1 do
For j:= i + 1 to n do
Begin
a:= x[i] - x[j]; a:= a * a;
b:= y[i] - y[j]; b:= b * b;
k:= a + b;
If k <= m * m then
Begin
c[i,j]:= sqrt(k);
c[j,i]:= sqrt(k);
End;
End;
For i:= 1 to w do
Begin
Readln(fi, u, v);
c[u,v]:= 0;
c[v,u]:= 0;
End;
Close(fi);
End;
Procedure Dijkstra;
Var
u,v,i: longint;
min: real;
Begin
Fillchar(free, sizeof(free), true);
For i:= 1 to n do d[i]:= max;
d[1]:= 0;
Repeat
u:= 0; min:= max;
For i:= 1 to n do
if free[i] and (min - d[i] > epsilon) then
Begin
min:= d[i];
u:= i;
End;
If (u = 0) or (u = n) then break;
free[u]:= false;
For v:= 1 to n do
if free[v] and (d[v] - d[u] - c[u,v] > epsilon)
then d[v]:= d[u] + c[u,v];
Until false;
End;
Procedure solve;
Var
fo: text;
Begin
Assign(fo, output);
Rewrite(fo);
If d[n] = max then writeln(fo, -1)
else writeln(fo, trunc(d[n] * 1000));
Close(fo);
End;
Begin
init;
LoadGraph;
Dijkstra;
solve;
End.