玄学优化暴力1秒内过

#include <bits/stdc++.h>
using namespace std;
struct node{
	int u,v,w;
}g[5000010];
int n,m,k,cnt,c[110],used,fa[20100];
long long ans=1e15;
bool vis[110];
int find(int x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
bool cmp(node x,node y){
	return x.w<y.w;
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	//freopen("road3.in","r",stdin);
	//freopen("road.out","w",stdout);
	
	cin>>n>>m>>k;
	clock_t start=clock();
	for(int i=1;i<=n+k;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[++cnt]={u,v,w};
	}
	
	for(int i=1;i<=k;i++){
		cin>>c[i];
		for(int j=1;j<=n;j++){
			int x;
			cin>>x;
			g[++cnt]={i+n,j,x};
		}
	}sort(g+1,g+1+cnt,cmp);
	for(int i=0;i<(1<<k);i++){
		clock_t now=clock();
		//cout<<now<<endl;
		if((double)(now-start)/1000>900) break;
		long long sum=0;
        int num=0;
        bool vis[20]={0};
        for(int j=1;j<=k;j++){
            if((i>>(j-1))&1){
                num++;
				vis[j]=1;
                sum+=c[j];
            }
            else vis[j]=0;
        }
        for(int j=1;j<=n+k;j++) fa[j]=j;
        int tot=0;
        //cout<<num<<"\n\n\n";
        for(int j=1;j<=cnt;j++){
        	int u=g[j].u,v=g[j].v,w=g[j].w;
        	
        	if(u>n&&!vis[u-n]) continue;
        	if(v>n&&!vis[v-n]) continue;
        	int fu=find(u),fv=find(v);
        	if(fu==fv) continue;
			//cout<<u<<" "<<v<<endl;
        	fa[fu]=fv;
        	sum+=w;
        	tot++;
        	if(tot==num+n-1) {
        		//cout<<sum<<endl;
        		ans=min(ans,sum);
        		break;
			}
		}
	}
	cout<<ans;
	return 0;
}