## Editorial for GONDOR

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

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
for i:=1 to n do
begin
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.


#### Code mẫu của happyboy99x

#include<cstdio>
#include<cfloat>
#include<cmath>
#include<queue>
using namespace std;

#define N 100
int x[N], y[N], s[N], n, receive[N][N-1];
double dis[N][N], dp[N];

inline int sqr(int x) { return x*x; }

int main() {
#ifdef __DONGOCKHANH__
freopen("input.txt", "r", stdin);
#endif
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
scanf("%d%d%d",x+i,y+i,s+i);
for(int j = 0; j < n - 1; --receive[i][j++])
dp[i] = DBL_MAX;
}
for(int i = 0; i < n; ++i)
for(int j = i+1; j < n; ++j)
dis[i][j] = dis[j][i] = sqrt(sqr(x[i] - x[j]) + sqr(y[i] - y[j]));
priority_queue<pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > qu;
dp[0] = 0; qu.push(make_pair((double) 0, 0));
while(!qu.empty()) {
double du = qu.top().first; int u = qu.top().second; qu.pop();
//printf("%d %.10lf\n", u+1, du);
if(du > dp[u]) continue;
for(int i = 0, cnt = 0; cnt < s[u] && i < n-1; ++i) {
//printf("v: %d %.10lf %d\n", v+1, dp[v] == DBL_MAX ? -1 : dp[v], cnt);
if(dp[v] < du) continue;
if(du + dis[u][v] < dp[v]) qu.push(make_pair(dp[v] = du + dis[u][v], v));
++cnt;
}
}
for(int i = 0; i < n; ++i) printf("%.10lf\n", dp[i]);
return 0;
}


#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define sqr(x) ((x) * (x))
#define di pair<double, int>
#define X first
#define Y second
const int N = 110;
const double oo = 1e12;
const double eps = 1e-6;
using namespace std;
long long X[N], Y[N];
double d[N];
bool was[N];
int n;

int main() {
ios :: sync_with_stdio(0); cin.tie(0);
cin >> n;
REP(i, 1, n) {
cin >> X[i] >> Y[i] >> S[i];
FOR(j, 1, n) cin >> adj[i][j];
}
priority_queue <di, vector<di>, greater<di> > Q;
REP(i, 2, n) d[i] = oo;
Q.push(di(0.0, 1));
while (!Q.empty()) {
int u = Q.top().Y; double du = Q.top().X; Q.pop();
if (fabs(du - d[u]) > eps) continue;
was[u] = true;
FOR(i, 1, n) {
if (S[u] == 0) break;
double uv = sqrt(sqr(X[u] - X[v]) + sqr(Y[u] - Y[v]));
if (!was[v]) {
if (d[v] > d[u] + uv) {
d[v] = d[u] + uv;
Q.push(di(d[v], v));
}
S[u]--;
}
}
}
REP(i, 1, n) cout << setprecision(6) << fixed << d[i] << '\n';
return 0;
}


{$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.  #### Code mẫu của hieult #include <cstdio> #include <cmath> //#include <conio.h> #include <iostream> #define max 10000000 using namespace std; struct diem { int x,y; }; int n,so[110],a[110][110],flag[110]; diem d[110]; double f[110]; double min(double a,double b) { return a<b?a:b; } double kc(diem A,diem B) { return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)); } int main() { //freopen("gondor.in.10","r",stdin); f[1] = 0; scanf("%d",&n); for(int i = 2;i<=n;i++) f[i] = max; for(int i = 1;i<=n;i++) { scanf("%d %d %d",&d[i].x,&d[i].y,&so[i]); for(int j = 1;j<=n-1;j++) scanf("%d",&a[i][j]); } memset(flag,0,sizeof(flag)); int u = 1,fl,danhdau; flag[1] = 1; while(true) { int t = 0; for(int i = 1;i<=n;i++) { if(!flag[a[u][i]]) { t++; f[a[u][i]]=min(f[a[u][i]],f[u]+kc(d[u],d[a[u][i]])); if(t==so[u]) break; } } fl = 1; double maxx = max; for(int i = 1;i<=n;i++) if(!flag[i] && f[i]<maxx) { fl = 0; danhdau = i; maxx = f[i]; } if(fl) break; else { flag[danhdau] = 1; u = danhdau; } // printf("%d\n",u); } for(int i = 1;i<=n;i++) printf("%lf\n",f[i]); //getch(); }  #### Code mẫu của ll931110 {$N+} {\$MODE DELPHI}
Program GONDOR;
Const
input  = '';
output = '';
maxn = 100;
maxd = 1000000;
Type
rec = record
x,y: integer;
end;
Var
heap,pos,s: array[1..maxn] of integer;
c: array[1..maxn] of rec;
des: array[1..maxn,1..maxn] of integer;
d: array[1..maxn] of double;
free: array[1..maxn] of boolean;
n,nHeap: integer;

Procedure init;
Var
f: text;
i,j: integer;
Begin
Assign(f, input);
Reset(f);

For i:= 1 to n do
Begin
For j:= 1 to n - 1 do read(f, des[i,j]);
End;

Close(f);
End;

Procedure update(v: integer);
Var
parent,child: integer;
Begin
child:= pos[v];
If child = 0 then
Begin
inc(nHeap);
child:= nHeap;
End;

parent:= child div 2;
While (parent > 0) and (d[heap[parent]] > d[v]) do
Begin
heap[child]:= heap[parent];
pos[heap[child]]:= child;

child:= parent;
parent:= child div 2;
End;

heap[child]:= v;
pos[v]:= child;
End;

Function pop: integer;
Var
r,c,v: integer;
Begin
pop:= heap[1];
v:= heap[nHeap];
dec(nHeap);

r:= 1;
While r * 2 <= nHeap do
Begin
c:= r * 2;
If (c < nHeap) and (d[heap[c + 1]] < d[heap[c]]) then inc(c);

If d[v] <= d[heap[c]] then break;
heap[r]:= heap[c];
pos[heap[r]]:= r;

r:= c;
End;

heap[r]:= v;
pos[v]:= r;
End;

Procedure solve;
Var
i,k,u,v: integer;
tmp: double;
Begin
Fillchar(free, sizeof(free), true);
free[1]:= false;

For i:= 1 to n do d[i]:= maxd;
d[1]:= 0;

nHeap:= 0;
update(1);

Repeat
u:= pop;
free[u]:= false;
k:= 0;

For i:= 1 to n - 1 do
Begin
v:= des[u,i];
If free[v] then
Begin
inc(k);
tmp:= sqr(c[u].x - c[v].x) + sqr(c[u].y - c[v].y);
tmp:= sqrt(tmp);

If d[v] > d[u] + tmp then
Begin
d[v]:= d[u] + tmp;
update(v);
End;
End;
If k = s[u] then break;
End;
Until nHeap = 0;
End;

Procedure printresult;
Var
f: text;
i: integer;
Begin
Assign(f, output);
Rewrite(f);
For i:= 1 to n do writeln(f, d[i]:0:10);
Close(f);
End;

Begin
init;
solve;
printresult;
End.