code

 avatar
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...