题解
真的想不到这题状压的做法。。。听说还有跑的飞快的模拟退火，要是现场做绝对滚粗QAQ。
不考虑深度，先预处理出 $pt_{i, S}$ 表示让一个不属于 集合 $S$ 的 点$i$ 与点集 $S$ 联通的最小代价， 也就是从 $i$ 到 $ j, j \in S$的最小距离。
接着处理$ss_{S, T}$, $S\subset T$, 表示从集合$S$拓展到$T$所需要的最小代价。
最后求出$f_{i, j}$ 表示当前已到 深度$i$, 已经扩展到集合$S$时耗费的最小代价. 答案就是$ \min(f_{i, U })$ $ i \in [0, n - 1]$
是可以求出所有的挖掘方案中的最小代价， 是个正确算法（吧,应该
代码
#include<cstring>
#include<algorithm>
#include<cstdio>
#define rd read()
#define rep(i,a,b) for( int i = (a); i <= (b); ++i )
#define per(i,a,b) for( int i = (a); i >= (b); --i )
using namespace std; const int N = ;
const int M = << ;
const int inf = ; int pt[N][M], ss[M][M], f[N][M], mp[N][N], n, m; inline int read() {
int X = , p = ; char c = getchar();
for(; c > '' || c < ''; c = getchar() ) if( c == '-' ) p = -;
for(; c >= '' && c <= ''; c = getchar() ) X = X * + c - '';
return X * p;
} inline void cmin( int &a, int b ) {
if( a > b ) a = b;
} int main()
{
n = rd; m = rd;
memset(pt, , sizeof(pt));
memset(f, , sizeof(f));
memset(mp, , sizeof(mp));
rep( i, , m ) {
int u = rd - , v = rd - , w = rd;//我从0开始存点
cmin( mp[u][v], w );
cmin( mp[v][u], w );
}
//求出点连到集合的最小代价
rep( S, , ( << n) - )
rep( i, , n - ) if((S >> i) & )
rep( j, , n - ) if(!((S >> j) & ))
cmin( pt[j][S], mp[j][i] );
//求出集合扩展的最小代价
rep( S, , ( << n) - )
for( int j = S & (S - ); j; j = S & (j - ) ) {//j为S 的子集，神奇的枚举子集方法
int left = S ^ j;
rep( i, , n - ) if((left >> i) & )
ss[j][S] = min( ss[j][S] + pt[i][j], inf );
} rep( i, , n - ) f[][ << i] = ;
rep( i, , n - )
rep( S, , ( << n) - )
for( int j = S & (S - ); j; j = S & (j - ) ) {
int tmp;
if( ss[j][S] != inf ) tmp = ss[j][S] * i;//集合能够扩展
else tmp = inf;
if( f[i - ][j] != inf ) cmin( f[i][S], f[i - ][j] + tmp );//上一步的状态可行
}
int ans = inf;
rep( i, , n - ) cmin( ans, f[i][ ( << n) - ] );//求出最小值
printf("%d\n", ans);
}