写了个记搜

rp++啊

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,x,y,z,dis[100][100],f[800100][20],vis[800100][20],s;
inline int read()
{
	int k=0,f=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) f|=c=='-';
	for(;isdigit(c);c=getchar()) k=(k<<1)+(k<<3)+(c^48);
	return f?-k:k;
}
inline int dfs(int st,int k)
{
	if(vis[st][k]) return f[st][k];
	for(int i=1;i<=n;i++)
	{
		if(i==k) continue;
		if(st&(1<<(i-1))) f[st][k]=max(f[st][k],dfs(st^(1<<(k-1)),i)+dis[i][k]);
	}
	vis[st][k]=1;
	return f[st][k];
}
signed main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			dis[i][j]=-1e12;
		}
	}
	for(int i=1;i<=m;i++)
	{
		x=read()+1,y=read()+1,z=read();
		dis[x][y]=max(dis[x][y],z);
	}
	vis[1][1]=1;
	for(int i=1;i<(1<<n);i++)
	{
		if(i&1&&i&(1<<(n-1)))
		{
			f[i][n]=dfs(i,n);
			s=max(s,f[i][n]);
		}
	}
	printf("%lld",s);
	return 0;
}