记录编号	49253	评测结果	AAAAA
题目名称	小树	最终得分	100
用户昵称	张来风飘	是否通过	通过
代码语言	Pascal	运行时间	0.109 s
提交时间	2012-11-07 15:40:32	内存使用	15.62 MiB

program project1;
var v:array[0..1005] of boolean;
    d1,d2:array[0..1005] of double;
    a,c:array[0..1005,0..1005] of double;
    t,n,m:longint;
procedure init;
begin
     assign(input,'treec.in');reset(input);
     assign(output,'treec.out');rewrite(output);
     read(t);
end;
procedure dijkstra1;
var i,u,j:longint;min:double;
begin
     fillchar(v,sizeof(v),0);
     v[0]:=true;
     for i:=0 to n-1 do d1[i]:=a[0,i];
     for i:=1 to n-2 do
     begin
          min:=1e30;u:=-1;
          for j:=0 to n-1 do if (not v[j])and(d1[j]<min) then
          begin
               min:=d1[j];
               u:=j;
          end;
          if u=-1 then break;
          v[u]:=true;
          for j:=0 to n-1 do if (not v[j]) and (d1[j]>d1[u]+a[u,j]) then
              d1[j]:=d1[u]+a[u,j];
     end;
end;
procedure dijkstra2;
var i,u,j:longint;min:double;
begin
     fillchar(v,sizeof(v),0);
     v[0]:=true;
     for i:=0 to n-1 do d2[i]:=c[0,i];
     for i:=1 to n-2 do
     begin
          min:=1e30;u:=-1;
          for j:=0 to n-1 do if (not v[j])and(d2[j]<min) then
          begin
               min:=d2[j];
               u:=j;
          end;
          if u=-1 then break;
          v[u]:=true;
          for j:=0 to n-1 do if (not v[j]) and (d2[j]>d2[u]+c[u,j]) then
              d2[j]:=d2[u]+c[u,j];
     end;
end;
procedure main;
var tt,i,j,x,y,w:longint;ans:double;
begin
     for tt:=1 to t do
     begin
          read(n);
          if n=1 then
          begin
                writeln('0.00');
                continue;
          end;
          for i:=0 to n-1 do
              for j:=0 to n-1 do
              begin
                   a[i,j]:=1e30;
                   c[i,j]:=1e30;
              end;
          for i:=1 to n-1 do
          begin
               read(x,y,w);
               a[x,y]:=w;
               c[x,y]:=1;
          end;
          if n=2 then
          begin
               writeln(w/1.0:0:2);
               continue;
          end;
          for i:=0 to n-1 do
          begin
               a[i,i]:=0;
               c[i,i]:=0;
          end;
          dijkstra1;
          dijkstra2;
          ans:=0;
          for i:=1 to n-1 do
          begin
               //if d2[i]=0 then begin writeln('error');halt;end;
               if d1[i]/d2[i]>ans then
               ans:=d1[i]/d2[i];
          end;
          writeln(ans:0:2);
     end;
     close(input);
     close(output);
end;
begin
     init;
     main;
end.