前置：状压 dp。

思路分析

首先注意到数据规模：$n\le 12$。显然可以依据此设计指数级算法。

显然最后拓展的道路和藏宝室构成一棵有根树，根节点为最先确定的藏宝室；如果最终答案不是树，就会出现环，我们可以将环上任意一条边去掉，均可以得到一个代价更小的方案。

我们考虑这样的一个过程：枚举最先打通的是那个藏宝室，将这个节点作为一棵树，然后不断加入新的节点，统计答案。

假定我们最终确定的方案中含有边 $(x,y)$（在树中 $x$ 是 $y$ 的父亲），根据题意，扩展这条道路的代价与两个因素有关：

• $x$ 的在树中的深度。

• $(x,y)$ 的长度，下文记为 $w(x,y)$。

记连接这棵树深度为 $i$ 和深度为 $i+1$ 的节点构成的边集为 $D_i$，则扩展这些边的总代价为 $i\times \sum_{(u,v)\in D_i}w(u,v)$。

通过上面的思考，可以发现，对于这些边，可以按照“深度”划分为若干个集合。据此启发，可以以“当前树的深度”为阶段，“已经有哪些点加入到了树中”为附加的状态来设计 dp。

设 $dp_{i,S}$ 表示树的深度为 $i$，且点集 $S$ 中的点均已加入这棵树，在此基础上代价的最小值。我们可以从第 $i$ 层拓展到第 $i+1$ 层，且 $i+1$ 层新加入了节点构成的点集为 $T$。

可以列出转移方程：

$$\large{dp_{i+1,S\cup T}\gets dp_{i,S}+i\times \text{cost}(S,T)}$$

$\text{cost(S,T)}$ 只考虑 $w(x,y)$，最小的能将 $T$ 中的节点与 $S$ 中节点相连的打通道路的方案的代价

转移的前提是：$S\cap T=\varnothing$，即 $S,T$ 无交。目标状态：当 $S=\{1,2,\dots,n\}$ 时，$dp_{k,S}$ 的 $\min$。

这个转移方程的实际含义：枚举第 $i+1$ 层节点 $T$ 和前 $i$ 层节点 $S$，然后将他们产生的代价和累加的前 $i$ 层的答案上。

注意到一个问题

$S$ 表示前 $i$ 层的节点，$T$ 表示第 $i+1$ 层的节点，怎样保证 $T$ 中所连接的节点都是第 $i$ 层的节点？如果 $S$ 中还包含 $i-1,i-2$ 层的节点，而计算花费时，却将 $T$ 和 $i-1,i-2$ 层的节点连接，并因此计算出错误的代价，这种情况如何避免？

在写这题时，这个问题也曾困扰过我。在蓝书中，有这样一句话让我恍然大悟。我们思考，假如 $\text{cost}(S,T)$ 计算的花费是不合法的花费，那么 $dp_{i+1,S\cup T}$ 会将 $dp_{i,S}$ 作为最优决策吗？

答案是否定的的，因为这样的转移会导致算得的答案比正确的 dp 值偏大，而正确的方案一定可以转移到，从而把错误的更新。

举个例子：

记最后的树的形态如上图，则当 $S=\{1,2,3,4\},T=\{5,6\}$ 时，则计算的总费用为：

$$w(1,2)+w(1,3)+w(2,4)\times 2+w(2,5)\times {\color{Red}3}+w(4,6)\times 3$$

但当 $S'=\{1,2,3,4,5\},T'=\{6\}$，此时计算的总费用为：

$$w(1,2)+w(1,3)+w(2,4)\times 2+w(2,5)\times {\color{Red}2}+w(4,6)\times 3$$

容易发现 $dp_{3,S},T$ 和 $dp_{3,S'},T'$ 这两种组合均可以更新出 $dp_{4,S\cup T}$，且后者的转移一定会比前者更优。所以不合法的转移一定对最终的答案没有影响。

Code

关于代码实现：

关于集合的运算可以用状压。

显然 $\text{cost}(S,T)$ 可以通过预处理实现，借助子集枚举的技巧，可以做到 $O(3^n)$ 枚举集合并枚举其子集，预处理时间复杂度 $O(3^n)$。虽然题目给出的边数很多，但可以用链接矩阵保留有用的边。

dp 部分，枚举初始点，枚举层数均为 $O(n)$，枚举状态并转移可以做到 $O(3^n)$，总时间复杂度 $O(n^23^n)$。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int M=(1<<12),inf=0x3f3f3f3f;
int cost[M][M],n,m,c[12][12];
long long dp[12][M],ans=inf;
void init(){
	for(int i=1;i<(1<<n);i++){
		for(int j=i;j;j=(j-1)&i){
			if(j==i)continue;
			for(int t=0,tmp;t<n;t++,tmp=inf){
				if(!(((i^j)>>t)&1))continue;
				for(int l=0;l<n;l++)if((j>>l)&1)tmp=min(tmp,c[l][t]);
				if(tmp>=inf){cost[j][i]=inf;break;}
                else cost[j][i]+=tmp;
			}
		}
	}
	return;
}
long long DP(int x){
    for(int i=0;i<12;i++)for(int j=0;j<M;j++)dp[i][j]=inf;//dp值取min,所以先清空
	dp[0][1<<x]=0;
	long long res=inf;
	for(int i=1;i<n;i++){
		for(int j=1;j<(1<<n);j++){
			for(int k=j;k;k=(k-1)&j){//枚举前i-1层的k和第i层的j
				if(k==j)continue;
				dp[i][j]=min(dp[i][j],dp[i-1][k]+1ll*i*cost[k][j]);
			}
			if(j==(1<<n)-1)res=min(res,dp[i][j]);
		}
	}
	return res;
}
int main(){
	scanf("%d %d",&n,&m);
	if(n==1){
		printf("0\n");
		return 0;
	}
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)c[i][j]=inf;
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d %d %d",&u,&v,&w),u--,v--;
		c[v][u]=c[u][v]=min(c[u][v],w);
	}
	init();
	for(int i=0;i<n;i++)ans=min(ans,DP(i));
	printf("%lld\n",ans);
	return 0;
}

如有错误，请指出。

记忆化搜索：

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f, N=15;
int a[N][N], n, m, f[N][N][1<<N], vis[N][N][1<<N],d[N];
//设 f(i,j,S)表示从 i 开始打通集合S，且 i 的深度为 j 时的最小代价

int dfs(int x,int dep,int S)
{
    if(!S)return f[x][dep][S]= 0;
    if(vis[x][dep][S])return f[x][dep][S];
    vis[x][dep][S]=1;
    
    f[x][dep][S]=inf;
    for(int y=1;y<=n;++y)if(S&d[y])
        if(a[x][y]!=inf)
            for(int s=S;s;s=(s-1)&S)if(s&d[y])
                f[x][dep][S]=min(f[x][dep][S], dfs(y,dep+1,s-d[y]) + dfs(x,dep,S-s)+dep*a[x][y]);
    return f[x][dep][S];
}
  
int main()
{
    scanf("%d%d", &n, &m);
	d[1]=1;for(int i=2;i<=n;++i)d[i]=d[i-1]*2;
    memset(a, 0x3f, sizeof a);
    for(int i=1,x,y,w;i<=m;++i)scanf("%d%d%d",&x,&y,&w),a[x][y]=a[y][x]= min(a[x][y],w);
    int ans=inf;
    for(int i=1;i<=n;++i)ans=min(ans,dfs(i,1,(1<<n)-1-d[i]));
    printf("%d\n", ans);
	return 0;
}

常规状态压缩版by qkw：

//develop by qkw
#include<bits/stdc++.h>
using namespace std;
const int N=13,M=4096,INF=0x01010101;//注意INF的设置，不能设置为0x3f3f3f3f
int a[N][N],g[M][M],f[N][M],ne[M],d[M];
int main(){
    memset(a,0x3f,sizeof(a));
    memset(f,0x3f,sizeof(f));
    int n,m;cin>>n>>m;
    int S=(1<<n)-1;
    for(int i=0;i<n;i++)d[1<<i]=i;//预处理d数组
    while(m--)
    {
        int x,y,v;
        cin>>x>>y>>v;x--,y--;
        if(a[x][y]>v)a[x][y]=a[y][x]=v;
    }
    //g[i][j]为已选点集状态为i，下一层加入的点集为j时新加入的所有点与原有点之间最小的边权之和
    for(int i=1;i<=S;i++)
    {
        int v=0,s=S^i;//i与j不能重复，故j只能从S^i中选
        for(int j=s;j;j=(j-1)&s)ne[j]=v,v=j;//逆序记录s的子点集
        for(int j=v;j;j=ne[j])//逆序枚举s的子点集
        {
            //在本层已有(j^(j&-j))点集时添加点(j&-j)后的最小边权
            int x=d[j&-j],y=INF;//x为当前点集j的最低位
            for(int k=0;k<n;k++)if(1<<k&i)y=min(y,a[x][k]);//枚举点x与原有点集i之间的最小边权
            g[i][j]=g[i][j^(j&-j)]+y;//在原有子集(j^x)中添加点x
        }
    }
    //f[i][j]为总层数为i，已选点集为j的最小答案
    for(int i=1;i<=S;i<<=1)f[0][i]=0;
    for(int i=1;i<n;i++)
        for(int j=1;j<=S;j++)
            for(int k=j;k;k=(k-1)&j)
                f[i][j]=min(f[i][j],f[i-1][j^k]+g[j^k][k]*i);//在i-1层的j^k点集中添加k点集作为下一层
    int v=0x3f3f3f3f;
    for(int i=0;i<=n;i++)
        v=min(v,f[i][S]);
    cout<<v<<endl;
    return 0;
}