题目分析：
这个做法不是最优的，想找最优解请关闭这篇博客。
首先容易想到用$f[i][S][j]$表示点$i$为根，考虑$S$这些点，$i$的深度为$j$情况的答案。
转移如下：
$f[i][S][j] = min(w(i,k)*(j+1)+f[k][S_0][j+1]+f[i][S-S_0][j])$ 其中$S != {i}$且$S_0 \subsetneqq S$且$k \in S_0$
$f[i][S][j] = 0$其中$S={i}$
这样已经可以通过了，时间复杂度是$O(n^3*3^n)$，原因是冗余状态太多。
但我们注意到对于每个集合我们都要遍历所有的为根的情况，用$g[i][S][j]$存储集合$S$中为根的最小值，可以优化到$O(n^2*3^n)$。
代码：
#include<bits/stdc++.h>
using namespace std; int n,m; int g[][]; int f[][<<][],gi[][<<][]; void read(){
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof(g));
for(int i=;i<=m;i++){
int x,y,v; scanf("%d%d%d",&x,&y,&v);
if(g[x][y] > v) g[x][y] = g[y][x] = v;
}
} void paint(int now,int S,int j){
for(int i=;i<=n;i++){
if((<<i-)&S) continue;
gi[i][S][j] = min(1ll*gi[i][S][j],f[now][S][j]+1ll*g[now][i]*j);
}
} void work(){
memset(f,0x3f,sizeof(f));memset(gi,0x3f,sizeof(gi));
for(int i=n-;i>=;i--){
for(int j=;j<=n;j++){
f[j][<<j-][i] = ;
paint(j,<<j-,i);
}
for(int S=;S<(<<n);S++){
int zeta = __builtin_popcount(S);
if(zeta > n-i || zeta <= ) continue;
for(int k=;k<=n;k++){
if(!((<<k-)&S)) continue;
for(int S1 = S;S1;S1 = (S1-)&S){
f[k][S][i] = min(gi[k][S1][i+]+f[k][S-S1][i],f[k][S][i]);
}
paint(k,S,i);
}
}
}
int ans = ;
for(int i=;i<=n;i++){
ans = min(ans,f[i][(<<n)-][]);
}
printf("%d",ans);
} int main(){
read();
work();
return ;
}