状压 DP
看到数据范围，因为 $1\leq n\leq12$，因此可以设计指数级算法（一般是搜索或状压 DP），考虑状压 DP。
状态设计
设 \(\textit{dp}_s\) 表示打通的宝藏屋的集合（宝藏屋的状态，且 $0\sim n-1$ 编号）为 $s$ 时的最小代价，$w_{i,j}$ 表示 $(i,j)$ 的长度。
那么转移就可以枚举 $s$ 中的每一个点 $i$，找到其连出的一条边 $(i,j)=w_{i,j}$，则有：
\[\textit{dp}_{s\cup\lbrace j\rbrace}\leftarrow\min(\textit{dp}_{s\cup\lbrace j\rbrace},\textit{dp}_s+w_{i,j}\cdot\textit{depth}_j)\]当然，也有直接得出答案的形式（枚举从 $j$ 打通到 $i$）：
\[\textit{dp}_s=\min_{i\in s}(\textit{dp}_{s-\lbrace i\rbrace}+\min_{j\in s-\lbrace i\rbrace}w_{i,j}\cdot \textit{depth}_{i})\]但是很显然，无论如何都绕不开 $\textit{depth}_i$ 或 $\textit{depth}_j$，而这在当前的 DP 状态下无法得知。
因此，对于这种不会的 DP，我们可以再加一维。
设 \(\textit{dp}_{i,s}\) 表示当前打通的宝藏屋的集合为 $s$，$s$ 中的宝藏屋最大深度为 $i$ 时的最小代价，答案即：
\[\min\limits_{i=0}^n\textit{dp}_{i,\mathbb N\cap[0,n-1]}\]状态转移
考虑到最后打通的肯定是一棵树，将这棵树按照深度分层，则递推 $\textit{dp}_{i,j}$ 即用第 $i-1$ 层的节点打通第 $i$ 层的节点。
枚举 $j$ 的非空真子集 $k$，设 $f_{k,j}$ 表示从状态为 $k$ 打通到 $j$ 的最小边权和，$\textit{can}_{k,j}$ 表示能否从 $k$ 打通到 $j$，有：
\[\textit{dp}_{i,j}=\min_{k\subsetneq j,\textit{can}_{k,j}=1}(\textit{dp}_{i-1,k}+i\cdot f_{k,j})\]考虑如何求出 $can_{k,j},f_{k,j}$。
显然，\(\textit{can}_{k,j}\) 不会总共 $2^{2n}$ 种状态都会用到（当然，你这样写也不会 TLE 就是了），因此可以在计算 $f_{k,j}$ 时计算。
枚举 $j$ 的真子集 $k$ 的时间复杂度是 $\mathcal O\left(3^n\right)$ 的，详见时间复杂度。
可以从枚举 $k$ 中的点 $l$，再枚举边 $(l,l’)$，从而得出 $k$ 能够到达的宝藏屋集合 $k’$，则 $can_{k,j}=\left[j\subseteq k’\right]$。其中的中括号为艾弗森括号，条件成立时为 $1$，否则为 $0$。
但是这样的总时间复杂度是 $\mathcal O\left(n^23^n\right)$ 的，可以优化。
记 $\textit{edge}_k$ 表示宝藏屋集合 $k$ 能打通的所有点的集合（包含 $k$），其实也就是上面的 $k’$，而求出所有的 $\textit{edge}_k$ 只需要 $\mathcal O\left(n^22^n\right)$。
这样其实是避免了重复求解 \(\textit{edge}_k\)，而 $\textit{can}_{k,j}=[j\subseteq edge_k]$。
得到 $can_{k,j}$ 后，若 $can_{k,j}=1$，就需要求解 $f_{k,j}$。
记 $v_x$ 表示节点 $x$ 能够到达的点的集合，有：
\[f_{k,j}=\sum_{y\in j-k}\min_{x\in v_y,x\in k,x\notin j}w_{x,y}\]即枚举 $(x,y)$，尝试从 $k$ 中的 $x$ 打通到在 $j$ 中且不在 $k$ 中的 $y$，且对于每一个 $y$，只需要一条边打通到它，因此要取所有边的最小值。
边界条件
\[\textit{dp}_{0,\lbrace i\rbrace}=0\]其中，$i$ 满足 $i\in \mathbb N\cap[0,n-1]$。
即题面中的“赞助商”打通的那个宝藏屋。
时间复杂度
枚举所有可能的宝藏屋集合 $s$ 的数量为 $2^n$，称全集 $U=\lbrace1,2,3,\cdots,n\rbrace$，$s$ 为 $U$ 的子集。
那么对于 $U$ 的子集，想要求得 $U$ 的子集的子集数，不妨先将其按元素个数分组。
有 $\dbinom n0$ 个大小为 $0$ 的集合（空集），有 $\dbinom n1$ 个大小为 $1$ 的集合，有 $\dbinom n2$ 个大小为 $2$ 的集合……有 $\dbinom ni$ 个大小为 $i$ 的集合。
由二项式定理，总子集数为：
\[\sum_{i=0}^n \binom ni2^i=\sum_{i=0}^n\binom ni1^{n-i}2^i=(1+2)^n=3^n\]还有一种分析方式。
记 $A\subseteq U,B\subseteq A$，答案即二元组 $(A,B)$ 的数量。对于元素 $x\in U$：
- $x\notin A,x\notin B$。
- $x\in A,x\notin B$。
- $x\in A,x\in B$。
故，总共有 $3^n$ 个子集。
那么，总时间复杂度为 $\mathcal O\left(n^23^n\right)$。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=12,inf=0x3f3f3f3f;
int n,g[N+1][N+1],dp[N+1][1<<N|1],f[1<<N|1][1<<N|1],can[1<<N|1][1<<N|1],edge[1<<N|1];
string binary(int x){
string ans;
while(x){
ans+=(x&1)^'0';
x>>=1;
}
reverse(ans.begin(),ans.end());
return ans;
}
main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int m;
cin>>n>>m;
memset(g,0x3f,sizeof(g));
while(m--){
int u,v,w;
cin>>u>>v>>w;
u--,v--;
g[u][v]=g[v][u]=min(g[u][v],w);
}
for(int s=0;s<(1<<n);s++){
edge[s]=s;
for(int i=0;i<n;i++){
if(s&(1<<i)){
for(int j=0;j<n;j++){
if(g[i][j]<inf){
edge[s]|=1<<j;
}
}
}
}
}
//从 j 转移到 i 的最小边权和
for(int i=0;i<(1<<n);i++){
for(int j=(i-1)&i;j;j=(j-1)&i){
//j 转移能到 i 的所有点
if((i&edge[j])==i){
can[j][i]=true;
static int tmp[N+1];
fill(tmp,tmp+n,inf);
for(int k=0;k<n;k++){
if(j&(1<<k)){
for(int l=0;l<n;l++){
if((i&(1<<l)) && !(j&(1<<l))){
tmp[l]=min(tmp[l],g[k][l]);
}
}
}
}
for(int k=0;k<n;k++){
if((i&(1<<k)) && !(j&(1<<k))){
if(tmp[k]==inf){
can[j][i]=false;
break;
}
f[j][i]+=tmp[k];
}
}
}else{
can[j][i]=false;
}
}
}
memset(dp,0x3f,sizeof(dp));
for(int i=0;i<n;i++){
dp[0][1<<i]=0;
}
for(int i=1;i<=n;i++){
for(int j=0;j<(1<<n);j++){
for(int k=(j-1)&j;k;k=(k-1)&j){
if(can[k][j]){
dp[i][j]=min(dp[i][j],dp[i-1][k]+i*f[k][j]);
}
}
}
}
int ans=2147483647;
for(int i=0;i<=n;i++){
ans=min(ans,dp[i][(1<<n)-1]);
}
cout<<ans<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
