GONDOR - GONDOR

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=101;
var n:longint;
    x,y,s:array[1..maxn] of longint;
    d:array[1..maxn] of real;
    free:array[1..maxn] of boolean;
    a:array[1..maxn,1..maxn] of longint;
    dist:array[1..maxn,1..maxn] of real;

procedure rf;
var i,j:longint;
begin
     read(n);
     for i:=1 to n do
     begin
          read(x[i],y[i],s[i]);
          for j:=1 to n-1 do read(a[i,j]);
     end;
     for i:=1 to n-1 do
         for j:=i+1 to n do
         begin
              dist[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
              dist[j,i]:=dist[i,j];
         end;
end;

procedure pr;
var i,x,y,j,k:longint; min:real;
begin
     for i:=1 to n do
     begin
          free[i]:=true; d[i]:=1234567890.0;
     end;
     d[1]:=0; free[1]:=false; x:=1;
     for i:=2 to n do
     begin
          j:=1;
          for k:=1 to s[x] do
          begin
               while not free[a[x,j]] and (j<=n-1) do inc(j);
               if j>n-1 then break;
               if d[a[x,j]]>d[x]+dist[a[x,j],x] then
                  d[a[x,j]]:=d[x]+dist[a[x,j],x];
               inc(j);
          end;
          min:=1234567889.0;
          for j:=1 to n do
              if free[j] and (d[j]<min) then
              begin
                   min:=d[j]; y:=j;
              end;
          free[y]:=false; x:=y;
     end;
end;

procedure wf;
var i:longint;
begin
     for i:=1 to n do writeln(d[i]:0:6);
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     rf;
     pr;
     wf;
     close(input); close(output);
end.

Download