题解

#include<bits/stdc++.h>
#define rg register
#define ci const int
#define cl const long long int
 
typedef long long int ll;
 
namespace IO {
	char buf[50];
}
 
template<typename T>
inline void qr(T &x) {
	char ch=getchar(),lst=' ';
	while(ch>'9'||ch<'0') lst=ch,ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	if (lst=='-') x=-x;
}
 
template<typename T>
inline void write(T x,const char aft,const bool pt) {
	if(x<0) {putchar('-');x=-x;}
	int top=0;
	do {
		IO::buf[++top]=x%10+'0';
		x/=10;
	} while(x);
	while(top) putchar(IO::buf[top--]);
	if(pt) putchar(aft);
}
 
template <typename T>
inline T mmax(const T a,const T b) {if(a>b) return a;return b;}
template <typename T>
inline T mmin(const T a,const T b) {if(a<b) return a;return b;}
template <typename T>
inline T mabs(const T a) {if(a<0) return -a;return a;}
 
template <typename T>
inline void mswap(T &a,T &b) {T temp=a;a=b;b=temp;}
 
 
const int maxn = 15;
const int maxm = 1010;
const int maxt = 1<<maxn;
const int INF = 0x3f3f3f3f;
 
int n,m,a,b,c,ans=INF;
int frog[maxt][maxn],gorf[maxt],dis[maxn][maxn];
 
int main() {
	qr(n);qr(m);
	memset(dis,0x3f,sizeof dis);
	for(rg int i=1;i<=m;++i) {
		a=b=c=0;qr(a);qr(b);qr(c);--a;--b;
		dis[b][a]=dis[a][b]=mmin(dis[a][b],c);
	}
	memset(frog,0x3f,sizeof frog);
	int all=(1<<n)-1;
	for(rg int i=1;i<=all;++i) {
		for(rg int j=0;j<n;++j) if(((1<<j)|i) == i) {
			dis[j][j]=0;
			for(rg int k=0;k<n;++k) if(dis[j][k]!=INF) {
				gorf[i]|=(1<<k);
			}
		}
	}
	for(rg int i=0;i<n;++i) frog[1<<i][0]=0;
	for(rg int i=2;i<=all;++i) {
		for(rg int s0=i-1;s0;s0=(s0-1)&i) if((gorf[s0]|i) == gorf[s0]) {
			int _sum=0;
			int ss=s0^i;
			for(rg int k=0;k<n;++k) if((1<<k)&ss) {
				int _temp=INF;
				for(rg int h=0;h<n;++h) if((1<<h)&s0) {
					_temp=mmin(_temp,dis[h][k]);
				}
				_sum+=_temp;
			}
			for(rg int j=1;j<n;++j) if(frog[s0][j-1]!=INF) {
				frog[i][j]=mmin(frog[i][j],frog[s0][j-1]+_sum*j);
			}
		}
	}
	for(rg int i=0;i<n;++i) ans=mmin(ans,frog[all][i]);
	write(ans,'\n',true);
	return 0;
}