GONDOR - GONDOR

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=101;
  oo=1000000000000;
var
  f1,f2:text;
  a:array[1..MAXN,1..MAXN] of longint;
  time,x,y:array[1..MAXN] of double;
  fin,hpos,h,s:array[1..MAXN] of longint;
  n,hsize:longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure inp;
var
  i,j:longint;
begin
  read(f1,n);
  for i:=1 to n do
    begin
      read(f1,x[i],y[i],s[i]);
      for j:=1 to n-1 do
        read(f1,a[i,j]);
    end;
end;
procedure ans;
var
  i:longint;
begin
  for i:=1 to n do
    writeln(f2,time[i]:0:10);
end;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure downHeap(i:longint);
var
  j:longint;
begin
  j:=i<<1;
  while (j<=hsize) do
    begin
      if (j<hsize) and (time[h[j+1]]<time[h[j]]) then inc(j);
      if (time[h[j]]<time[h[i]]) then
        begin
          swap(hpos[h[i]],hpos[h[j]]);
          swap(h[i],h[j]);
        end;
      i:=j; j:=i<<1;
    end;
end;
procedure upHeap(i:longint);
var
  j:longint;
begin
  j:=i>>1;
  while (i>1) and (time[h[i]]<time[h[j]]) do
    begin
      swap(hpos[h[i]],hpos[h[j]]);
      swap(h[i],h[j]);
      i:=j; j:=i>>1;
    end;
end;
procedure push(u:longint);
begin
  inc(hsize); h[hsize]:=u; hpos[u]:=hsize;
  upHeap(hsize);
end;
procedure pop(var u:longint);
begin
  u:=h[1]; hpos[u]:=1;
  swap(h[1],h[hsize]); hpos[h[1]]:=1;
  dec(hsize); downHeap(1);
end;
function dist(x1,y1,x2,y2:double):double;
begin
  dist:=sqrt(sqr(x1-x2)+sqr(y1-y2));
end;
procedure solve;
var
  count,u,v,i:longint;
begin
  hsize:=0; push(1);
  for u:=2 to n do time[u]:=oo;
  while hsize>0 do
    begin
      pop(u); count:=0; fin[u]:=1;
      for i:=1 to n-1 do
        begin
          v:=a[u,i];
          if fin[v]=0 then inc(count);
          if time[v]>time[u]+dist(x[u],y[u],x[v],y[v]) then
            begin
              time[v]:=time[u]+dist(x[u],y[u],x[v],y[v]);
              if hpos[v]=0 then push(v)
              else upHeap(hpos[v]);
            end;
          if count=s[u] then break;
        end;
    end;
end;
begin
  openF;
  inp;
  solve;
  ans;
  closeF;
end.

Download