24pts玄关求调

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=2e5+5,M=1e7+5;
struct node
{
	int u,v,w;
}e[M],g[M];
bool operator < (node x,node y){
	return x.w<y.w;
}
int v[20];
int t;
int fa[N];
int getpa(int x)
{
	if(fa[x]==x)
	{
		return x;
	}
	else
	{
		return fa[x]=getpa(fa[x]);
	}
}

signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		cin>>e[i].u>>e[i].v>>e[i].w;
	}
	sort(e+1,e+m+1);
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		if(getpa(e[i].u)==getpa(e[i].v))
		{
			continue;
		}
		t++;
		g[t]=e[i];
		fa[getpa(e[i].u)]=getpa(e[i].v);
	}
	for(int i=1;i<=k;i++)
	{
		cin>>v[i];
		for(int j=1;j<=n;j++)
		{
			int x;
			cin>>x;
			t++;
			g[t]=(node){n+i,j,x};
//			n+i,j,x
		}
	}
	sort(g+1,g+t+1);
	int ans=INT_MAX;
	for(int j=0;j<(1<<k);j++)
	{
		int sum=0;
		for(int i=0;i<k;i++) 
		{
			if(j&(1<<i)) 
			{
				sum+=v[i+1];	
			}
		}
		for(int i=1;i<=n+k;i++)
		{
			fa[i]=i;
		}
		for(int i=1;i<=t;i++){
			if(g[i].u>n && !(j&(1<<(g[i].u-n-1)))) 
			{
				continue;
			}
			if(getpa(g[i].u)==getpa(g[i].v))
			{
				continue;
			}
			sum+=g[i].w;
			fa[getpa(g[i].u)]=getpa(g[i].v);
		}
		ans=min(ans,sum);
	}
	return 0;
}