题意：
思路：n<=12，考虑状压DP
生成树中深度相同的点可以一次性转移完毕
设dp[sta,i]为已转移完sta状态的点，当前深度为i的最小花费
dp[sta or v,i+1]=min(dp[sta,i]+f[sta,v]*(i+1))，其中v是sta关于全集(1<<n)-1的补集v1的一个子集，这一步需要枚举子集
考场上写的O(3^n*n^2)，没有预处理f[sta,v]而是每次都算了一遍，有进一步优化的空间
const max=;
var dp,dis:array[..,..]of int64;
f:array[..,..]of int64;
n,m,i,j,x,y,z,k,maxs,v,v1:longint;
s,ans:int64; function min(x,y:int64):int64;
begin
if x<y then exit(x);
exit(y);
end; begin
assign(input,'treasure.in'); reset(input);
assign(output,'treasure.out'); rewrite(output);
readln(n,m);
for i:= to n do
for j:= to n do f[i,j]:=<<;
for i:= to n do f[i,i]:=;
for i:= to m do
begin
readln(x,y,z);
f[x,y]:=min(f[x,y],z);
f[y,x]:=min(f[y,x],z);
end;
maxs:=(<<n)-;
for i:= to maxs do
for j:= to n do
if i and (<<(j-))= then
begin
dis[i,j]:=<<;
for k:= to n do
if (j<>k)and(i and (<<(k-))>) then dis[i,j]:=min(dis[i,j],f[j,k]);
end; m:=maxs;
for i:= to maxs do
for j:= to n+ do dp[i,j]:=<<;
for i:= to n do dp[<<(i-),]:=;
for i:= to n do
for j:= to maxs do
begin
v:=j xor m; v1:=v;
while v> do
begin
s:=;
for k:= to n do
if v and (<<(k-))> then
begin
s:=s+dis[j,k];
if s>=(<<) then break;
end;
if s<(<<) then
dp[j or v,i+]:=min(dp[j or v,i+],dp[j,i]+s*(i+));
v:=v1 and (v-);
end;
end;
ans:=<<;
for i:= to n+ do ans:=min(ans,dp[maxs,i]);
if n= then ans:=;
writeln(ans); close(input);
close(output);
end.
O(3^n*n)，预处理两个值
d[sta,i] 已取sta状态中的点到i点的最小值 预处理O（2^n*n^2）
f[x,y] x状态中的点和y状态中的所有点连接最小长度之和=f[x,y-lowbit(y)]+d[x,z]，z表示y中最后一个1的位置 预处理O（4^n） 需要保证x与y没有交集
const max=;
var dp,d:array[..,..]of int64;
dis:array[..,..]of int64;
f:array[..,..]of int64;
num:array[..]of longint;
n,m,i,j,x,y,z,k,maxs,v,v1:longint;
s,ans:int64; function min(x,y:int64):int64;
begin
if x<y then exit(x);
exit(y);
end; function lowbit(x:longint):longint;
begin
exit(x and (-x));
end; begin
assign(input,'treasure.in'); reset(input);
assign(output,'treasure.out'); rewrite(output);
readln(n,m);
for i:= to n do
for j:= to n do f[i,j]:=<<;
for i:= to n do f[i,i]:=;
for i:= to m do
begin
readln(x,y,z);
f[x,y]:=min(f[x,y],z);
f[y,x]:=min(f[y,x],z);
end; maxs:=(<<n)-;
for i:= to maxs do
for j:= to n do
if i and (<<(j-))= then
begin
d[i,j]:=<<;
for k:= to n do
if (j<>k)and(i and (<<(k-))>) then d[i,j]:=min(d[i,j],f[j,k]);
end; m:=maxs;
for i:= to do num[<<(i-)]:=i;
for i:= to maxs do
for j:= to maxs do dis[i,j]:=<<;
for i:= to maxs do dis[,i]:=;
for i:= to maxs do dis[i,]:=; for i:= to maxs do
for j:= to maxs do
if i and j= then
begin
x:=num[lowbit(j)];
dis[i,j]:=dis[i,j-lowbit(j)]+d[i,x];
if dis[i,j]>(<<) then dis[i,j]:=<<;
end; for i:= to maxs do
for j:= to n+ do dp[i,j]:=<<;
for i:= to n do dp[<<(i-),]:=;
for i:= to n do
for j:= to maxs do
begin
v:=j xor m; v1:=v;
while v> do
begin
if dis[j,v]<<< then
dp[j or v,i+]:=min(dp[j or v,i+],dp[j,i]+dis[j,v]*(i+));
v:=v1 and (v-);
end;
end; ans:=<<;
for i:= to n+ do ans:=min(ans,dp[maxs,i]);
if n= then ans:=;
writeln(ans); close(input);
close(output);
end.