记录编号	596634	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2017]宝藏	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	1.225 s
提交时间	2024-10-31 15:20:10	内存使用	15.36 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,ll>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 20,M = (1 << 13) + 2;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}

int n,m;
ll f[N][M];
int s[M][M],d[N][N];

void work(int p,int now){
	int sum = 0;
	for(int i = 0;i < n;i++){
		if(!(now >> i & 1) || (p >> i & 1))continue;
		int mi = 0x3f3f3f3f;
		for(int j = 0;j < n;j++){
			if(i == j || !(p >> j & 1))continue;
			mi = min(mi,d[i + 1][j + 1]);
		}
		if(mi == 0x3f3f3f3f)return s[p][now] = -1,void();
		sum += mi;
	}
	s[p][now] = sum;
}

int main(){
	freopen("2017treasure.in","r",stdin);
	freopen("2017treasure.out","w",stdout);
	n = read(),m = read();
	if(n == 1)return printf("0\n"),0;
	memset(d,0x3f,sizeof d);
	for(int i = 1;i <= m;i++){
		int x = read(),y = read(),z = read();
		d[x][y] = d[y][x] = min(d[x][y],z);
	}
	memset(f,0x3f,sizeof f);
	f[0][0] = 0;
	for(int i = 0;i < n;i++)f[0][1 << i] = 0;
	ll ans = 1e17;
	for(int i = 1;i <= n;i++){
		for(int now = 1;now < (1 << n);now++){
			for(int p = now;p;--p &= now){
				if(now == p)continue;
				if(f[i-1][p] == 0x3f3f3f3f)continue;
				if(s[p][now] == 0)work(p,now);
				if(s[p][now] == -1)continue;
				f[i][now] = min(f[i][now],f[i-1][p] + (ll)i * s[p][now]);
			}
 		}
 		ans = min(ans,f[i][(1 << n) - 1]);
	}
	printf("%lld\n",ans);

	return 0;

}