算法3

这是叶枫的代码，https://www.acwing.com/solution/content/5158/
增加一个剪枝，A*+DFS。

计算每个点的与其它点的最小距离，用它来估算剩余结点的最优费用。
这样改动少，而且速度提升明显，只需41ms就AC

C++ 代码

#include <bits/stdc++.h>
using namespace std;

//对叶枫的https://www.acwing.com/solution/content/5158/ 进行个人风格的修改，以便理解
const int INF=0x01010101;
int g[15][15],mdst[15],n,m,ans=INF; //g:图的连接表,mdst:每个点最小的连接距离
int lay[15][15], nlay[15];//lay:每层第i个是哪个点,nlay:每层多少个点
bool used[15];//每个点是否被用过

//返回值无用，但方便编程，
inline int dfs(int ceng,int k,int cnt,int sum,int rem){
    //现在第ceng层，讨论结点k，总共用了cnt个点，现在这棵树价值sum，剩余点的总最小距离rem
    if(sum+rem*ceng>=ans)return 0;//最优性剪枝   ！！！最重要！！！只要现阶段不是最小的了就没有继续的必要了

    if(nlay[ceng-1]==0)return 0;//上一层没有选入点（上层为空），树不可能继续构建，该可能不合法，直接跳过

    if(cnt==n) return ans=min(sum,ans);//所有点都已经被构建进树中，更新答案，结束这种可能

    if(k>n) return dfs(ceng+1,1,cnt,sum,rem);//该层所有点都讨论过一遍，继续下一层

    if(used[k]==1) return   dfs(ceng,k+1,cnt,sum,rem);//该点已用，直接讨论下一个点

    used[k]=1;  //能算到这里，该点没用过，用下试试
    int mini=INF;//找到该点与上层的最小联系
    for(int i=1;i<=nlay[ceng-1];i++)//若与上层所有点不连通，则mini是INF,会被最优性剪枝减去
        mini=min(mini,g[k][lay[ceng-1][i]]);
    nlay[ceng]++;//这层又多一个点啦
    lay[ceng][nlay[ceng]]=k;//这点是哪个？存在   lay[哪层][第几个]   中
    dfs(ceng,k+1,cnt+1,sum+mini*ceng,rem-mdst[k]);//选用此点（可能1）

    nlay[ceng]--; //恢复数据，以备下一个dfs
    used[k]=0;  //不用此点（可能2）
    return dfs(ceng,k+1,cnt,sum,rem);
}
int main(){
    cin>>n>>m;
    memset(g,1,sizeof g);//数组初始化,每个都=0x01010101，不能用0x3f，参与运算会overflow
    memset(mdst,1,sizeof mdst);
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        if(a==b)continue;
        g[a][b]=g[b][a]=min(g[a][b],c);//无向图双向赋值，只取最小值
        mdst[a]=min(mdst[a],c), mdst[b]=min(mdst[b],c);
    }
    int sum=0;
    for(int i=1;i<=n;i++)sum+=mdst[i];
    for(int i=1;i<=n;i++){//每个点都当一次根
        used[i]=1;//点已用
        lay[0][1]=i;//根看做第0层
        nlay[0]=1;//0层有一个根节点
        dfs(1,1,1,0,sum-mdst[i]);//从第一层开始搜索
        used[i]=0;//以该点为根的数搜索完毕
    }
    cout<<ans;
    return 0;
}