如下. 思路:用一个数x(二进制)代表已发掘的藏宝洞,对边进行去重简化,然后剪枝(如果现在状态为x且花费大于目前状态为x是的最优解则剪枝),但是WA on 11

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct edge{
	int to,w;
	edge(int T,int W){
		to=T;w=W;
	}
};
vector<edge>li[100005];
bool cmp1(edge a,edge b){
	if(a.to!=b.to)return a.to<b.to;
	return a.w<b.w;
}
bool cmp2(edge a,edge b){
	return a.w<b.w;
}
int minn=1145141919,n,m,a,b,c,mimn=1145141919;
int x=0;
int dis[100005];
int best[100005],b2[100005];
int tar[100005];
void dfs(long long x,int p){
	
	if(p>=minn)return;
	if(p>=b2[x])return;
	
	b2[x]=min(b2[x],p);
	if(x==(1<<(n+1))-2){
		
//	cout<<"Search "<<x<<" "<<"with the price of "<<p<<endl;
		minn=min(minn,p);
		return;
	}
	for(int i=1;i<=n;i++){
		if(x&(1<<i)){
			for(int j=0;j<li[i].size();j++){
				if((!(x&(1<<li[i][j].to)))&&(!dis[li[i][j].to])){
					dis[li[i][j].to]=dis[i]+1;
					int x2=x|(1<<li[i][j].to);
					dfs(x|(1<<li[i][j].to),p+dis[i]*li[i][j].w);
					dis[li[i][j].to]=0;
				}
			}
		}
	}
}
signed main(){
	memset(best,0,sizeof(best));
	cin>>n>>m;
	if(m==0){
		cout<<0;
		return 0;
	}
	for(int i=1;i<=m;i++){
		cin>>a>>b>>c;
		edge e=edge(1,2);
		e.to=b;
		e.w=c;
		li[a].push_back(e);
		e.to=a;
		li[b].push_back(e);
	}

	for(int i=1;i<=n;i++)sort(li[i].begin(),li[i].end(),cmp1);
	
/*	for(int i=1;i<=n;i++){
		for(int j=0;j<li[i].size();j++)cout<<"("<<li[i][j].to<<","<<li[i][j].w<<") ";
		cout<<endl;
	}
	cout<<endl;*/
	for(int i=1;i<=n;i++){
		edge e=li[i][0];
		for(int j=1;j<li[i].size();j++){
			if(li[i][j].to==e.to)li[i].erase(li[i].begin()+j),j--;
			else e=li[i][j];
		}
		sort(li[i].begin(),li[i].end(),cmp2);
	}
/*	for(int i=1;i<=n;i++){
		for(int j=0;j<li[i].size();j++)cout<<"("<<li[i][j].to<<","<<li[i][j].w<<") ";
		cout<<endl;
	}*/
	memset(b2,127,sizeof(b2));
	minn=114514191;
//	cout<<n<<endl;
	for(int i=1;i<=n;i++){
			dis[i]=1;
			dfs(1<<i,0);
			dis[i]=0;
	}
	cout<<minn<<endl;
}