80pts TLE#20-25求助

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,res=0,ans=0,c[15][10010],minn=0;
bool flag=0,vis[15];
struct edge{
	int u,v;
	long long w;
}edges[1000010];
vector<edge> vec;
struct node{
	int fa;
}a[1000010];
int cmp(edge x,edge y){
	return x.w<y.w;
}
int find(int k){
	if(a[k].fa!=k) return a[k].fa=find(a[k].fa);
	else return k;
}
void kruskal(int ls1){
	ans=0;
	sort(edges+1,edges+m+1,cmp);
	for(int i=1;i<=ls1;i++) a[i].fa=i;
	for(int i=1;i<=m;i++){
		if(find(a[edges[i].u].fa)!=find(a[edges[i].v].fa)){
			a[find(edges[i].u)].fa=find(edges[i].v);
			res+=edges[i].w;
			ans++;
			if(ls1==n) vec.push_back({edges[i].u,edges[i].v,edges[i].w});
		}else continue;
		if(ans==ls1-1){
			if(ls1==n){
				for(int j=0;j<vec.size();j++) edges[j+1].u=vec[j].u,edges[j+1].v=vec[j].v,edges[j+1].w=vec[j].w;
    		for(int j=vec.size()+1;j<=m;j++) edges[j].u=0,edges[j].v=0,edges[j].w=0;
            //这里是缩边操作m->n-1;
			}
			break;
		}
	}
}
void sol(){//对每个元组跑一遍最小生成树
	long long ls=0;
	int cnt=0;
	for(int j=0;j<vec.size();j++) edges[j+1].u=vec[j].u,edges[j+1].v=vec[j].v,edges[j+1].w=vec[j].w;
	for(int j=vec.size()+1;j<=m;j++) edges[j].u=0,edges[j].v=0,edges[j].w=0;
	for(int i=1;i<=k;i++){
		if(vis[i]){
			cnt++;
			ls+=c[i][1];
			for(int j=2;j<=n+1;j++){
				m++;
				edges[m].u=n+cnt,edges[m].v=j-1,edges[m].w=c[i][j];//将城市化的乡村视为新点加入图
			}
		}else continue;
	}
	res=0;
	kruskal(n+cnt);
	if(res+ls<minn) minn=res+ls;
}
void dfs(int l,int r){//枚举元组
	if(l>k){
		m=n-1;
		sol();
		return;
	}
	vis[l]=1;
	dfs(l+1,0);
	vis[l]=0;
	dfs(l+1,1);
}
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) a[i].fa=i;
	for(int i=1;i<=m;i++) cin>>edges[i].u>>edges[i].v>>edges[i].w;
	for(int i=1;i<=k;i++)
		for(int j=1;j<=n+1;j++) cin>>c[i][j];
	kruskal(n);
	minn=res;
	m=n-1;
	dfs(1,1);//枚举元组
	cout<<minn;
	return 0;
}