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.

Download