C++ 解法, 执行用时: 896ms, 内存消耗: 39544K, 提交时间: 2022-02-17 20:44:30

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mo 998244353
const int N=20,M=3e5+10;
int n,m,w[N][N],h[N][M],ct[M],ans[N][M];
void fmt(int *d,int op)
{
	for(int i=1;i<(1<<n);i<<=1)
		for(int j=0;j<(1<<n);j++)
			if(i&j)d[j]=(d[j]+1ll*op*d[i^j]+mo)%mo;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i!=j)w[i][j]=1e9;
	for(int x,y,z,i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		w[x][y]=min(w[x][y],z);
		w[y][x]=min(w[y][x],z);
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(i!=j&&i!=k&&j!=k)
					w[i][j]=min(w[i][j],w[i][k]+w[k][j]);
	for(int s=1;s<(1<<n);s++)
	{
		h[ct[s]=ct[s>>1]+(s&1)][s]=1e9;
		for(int i=1;i<=n;i++)
			if(s&(1<<i-1))
			{
				int s1=0;
				for(int j=1;j<=n;j++)
					if(s&(1<<j-1))s1+=w[i][j];
				h[ct[s]][s]=min(h[ct[s]][s],s1+1);
			}
	}
	ans[0][0]=1;
	fmt(ans[0],1);
	for(int i=1;i<=n;i++)
	{
		fmt(h[i],1);
		for(int j=0;j<i;j++)
			for(int s=0;s<(1<<n);s++)
				ans[i][s]=(ans[i][s]+1ll*ans[j][s]*h[i-j][s]%mo)%mo;
		fmt(ans[i],-1);
		for(int s=0;s<(1<<n);s++)
			if(ct[s]!=i)ans[i][s]=0;
		if(i!=n)fmt(ans[i],1);
	}
	fmt(ans[n],-1);
	printf("%d",ans[n][(1<<n)-1]);
	return 0;
}