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.

Download