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.