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.