记录编号	9807	评测结果	WWWTTEETTT
题目名称	[RQNOJ 184] 洞窟探索	最终得分	0
用户昵称	0彼岸0	是否通过	未通过
代码语言	Pascal	运行时间	5.096 s
提交时间	2009-04-21 11:33:42	内存使用	0.20 MiB

Program hole;
Const
   fin='hole.in';
   fou='hole.out';
   maxn=150;
   maxm=100;
Type node=record
             p,len:longint;
          end;
var
   e:array[1..maxn,1..3]of node;
   en:array[1..maxn]of integer;
   a:array[1..maxn,1..maxn]of longint;
   list:array[1..maxm]of longint;
   now,ll,n,m,i,j,k:longint;
   b:array[1..maxn]of boolean;
   min,temp:real;
   good:array[1..3]of real;
   pp:array[1..3]of longint;
Procedure init;
var i,x,y,l,j,k:longint;
begin
   assign(input,fin);  reset(input);
   assign(output,fou); rewrite(output);
   readln(n,m);
   fillchar(e,sizeof(e),0);
   fillchar(en,sizeof(en),0);
   fillchar(a,sizeof(a),0);
   for i:=1 to n-1 do
   begin
      readln(x,y,l);
      inc(en[x]);
      e[x,en[x]].p:=y;
      e[x,en[x]].len:=l;
      inc(en[y]);
      e[y,en[y]].p:=x;
      e[y,en[y]].len:=l;

      a[x,y]:=l;
      a[y,x]:=l;
   end;

   for i:=1 to n do
     for j:=1 to n do
       for k:=1 to n do
       begin
          if (a[j,k]=0)or((a[j,k]>a[j,i]+a[i,k])and(a[j,i]<>0)and(a[i,k]<>0)) then
            a[j,k]:=a[j,i]+a[i,k];
       end;
   fillchar(list,sizeof(list),0);
   fillchar(b,sizeof(b),0);
   ll:=0;
end;

Function doit(k,q:longint):boolean;
var i,p,j,kk,now:longint;
begin
   if q=0 then exit(true);
   inc(ll);
   list[ll]:=k;
   b[k]:=true;
   for i:=1 to en[k] do
   begin
      if b[e[k,i].p] then continue;
      inc(ll);
      list[ll]:=e[k,i].p;
      now:=0;
      for j:=1 to ll do
      begin
         for kk:=j+1 to ll do
         begin
            inc(now,a[list[j],list[kk]]);
         end;
      end;
      good[i]:= now / ((ll*(ll-1))>>1);
      pp[i]:=i;
      dec(ll);
   end;

   for i:=1 to en[k]-1 do
     for j:=i+1 to en[k] do
     begin
        if good[i]>good[j] then
        begin
           temp:=good[i]; good[i]:=good[j]; good[j]:=temp;
           now:=pp[i]; pp[i]:=pp[j]; pp[j]:=now;
        end;
     end;
   for i:=1 to en[k] do
   begin
      if doit(e[k,pp[i]].p,q-1) then exit(true);
   end;
   dec(ll);
   b[k]:=false;
   exit(false);
end;

begin
   init;
   doit(1,m);
   now:=0;
   for j:=1 to ll do
   begin
      for k:=j+1 to ll do
      begin
         inc(now,a[list[j],list[k]]);
      end;
   end;
   writeln( (now / ((ll*(ll-1))>>1)):0:2);
   close(output);
end.