80pts求调

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+1e5+1,M=1e4+11;
struct node{ll st,to,wg,id;}edge[N],cal[M*11];
ll n,m,k,u,v,w,fa[M],ans,cnt,costt[11][M],res,len;
bool cmp(node x,node y){return x.wg<y.wg;}
ll find(ll x){
	if (fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void merge(ll x,ll y){fa[find(x)]=find(y);}
int main(){
	cin>>n>>m>>k;
	ans=0;
	for (ll i=1;i<=M;i++) fa[i]=i;//初始化并查集
	for (ll i=1;i<=m;i++){//输入最初的边
		cin>>u>>v>>w;
		edge[i].st=u;
		edge[i].to=v;
		edge[i].wg=w;
	}
	//预处理最小生成树，并把这个最小生成树的边存进数组
	sort(edge+1,edge+m+1,cmp);
	for (ll i=1;i<=m;i++){
		ll x=edge[i].st,y=edge[i].to,z=edge[i].wg;
		if (find(x)!=find(y)){
			merge(x,y);
			ans+=z;
      		edge[++len].st=x;
      		edge[len].to=y;
      		edge[len].wg=z;
      		edge[len].id=0;
		}
	}
    //输入边并且再次排序
	for (ll i=1;i<=k;i++)
	for (ll j=0;j<=n;j++){
		cin>>costt[i][j];
        if (j==0) continue;
        edge[++len].st=i+n;
        edge[len].to=j;
        edge[len].wg=costt[i][j];
        edge[len].id=i;
	}
    sort(edge+1,edge+len+1,cmp);
	res=ans; 
	//暴力枚举每种情况 
	for (ll i=1;i<(1<<k);i++){
		ll j=i,l=k,st[20],cost=0,flag=1,cntt=0,sizee=0,v[21];
		memset(st,0,sizeof(st));
        memset(v,0,sizeof(v));
		for (ll a=1;a<=M;a++) fa[a]=a;
		while (j){
			st[l]=j%2;
			l--;
			j/=2;
		}
		for (ll a=1;a<=k;a++)
		if (st[a]==1){
			cntt++;
			cost+=costt[a][0];
            v[a]=1;
			if (cost>=res){
				flag=0;
				break;
			}
		}
		if (flag==0) continue;
        for (ll a=1;a<=len;a++)
        if (edge[a].id==0 || v[edge[a].id]==1){
			cal[++sizee].st=edge[a].st;
			cal[sizee].to=edge[a].to;
			cal[sizee].wg=edge[a].wg;
		}
		for (ll a=1;a<=sizee;a++){
			ll x=cal[a].st,y=cal[a].to,z=cal[a].wg;
			if (find(x)!=find(y)){
				merge(x,y);
				cost+=z;
			}
		}
		res=min(cost,res);
	}
	cout<<res;
}