code
unknown
pascal
3 years ago
1.8 kB
4
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...