code
unknown
pascal
4 years ago
1.8 kB
15
Indexable
var t,c,i,ii,j,k:longint;
l,r:qword;
n,u,v,dem,so:word;
max:real;
a:array[1..500,1..500] of longint;
len:array[1..500] of longint;
p:array[1..500] of longint;
s:array[1..500] of byte;
kt:boolean;
begin
readln(t);
kt:=true;
for i:=1 to t do
begin
readln(n);max:=0;t:=0;
for j:=1 to n-1 do
begin
readln(u,v,c);
a[u,v]:=c;
a[v,u]:=c;
inc(t,c+c);
end;
readln(f,l,r);
for j:=1 to n do
for k:=1 to n do
if (j<>k) and (a[j,k]=0) then a[j,k]:=t;
for j:=1 to n do
begin
fillchar(s,sizeof(s),0);
for k:=1 to n do
begin
len[k]:=t;
p[k]:=j;
end;len[j]:=0;
while kt do
begin
for k:=1 to n do
if (s[k]=0) and (len[k]<t) then break;
if (s[k]<>0) or (len[k]>=t) then break;
for ii:=1 to n do
if (s[ii]=0) and (len[ii]<len[k]) then k:=ii;
s[k]:=1;
for ii:=1 to n do
if (s[ii]=0) and (len[ii]>len[k]+a[ii,k]) then
begin
p[ii]:=k;
len[ii]:=len[k]+a[ii,k];
end;
end;
for k:=1 to n do
if (len[k]>=l) and (len[k]<=r) then
begin
dem:=0;so:=k;
while so<>j do
begin
inc(dem);
so:=p[so];
end;
if len[k]/dem>max then max:=len[k]/dem;
end;
end;
writeln(max:1:3);
end;
readln;
end.Editor is loading...