最大点为啥1.6s

#include <bits/stdc++.h>
using namespace std;
long long n,m,k,fa[10020],c[15],vis[15],ans;
struct edge{int u,v,w;};
edge g[1000010];//原图
vector <edge> l;//新图
void init(){for(int i=1;i<=n+k;i++)fa[i]=i;}//注意初始化到n+k
int _find(int x){return fa[x]==x?x:fa[x]=_find(fa[x]);}
void _union(int x,int y){
    int fx=_find(x),fy=_find(y);
    if(fx==fy) return ;
    fa[fx]=fy;
}//并查集操作
bool cmp(edge x,edge y){return x.w<y.w;}
void tree(){//新图跑最小生成树
    long long sum=0;
    for(int i=1;i<=k;i++){if(vis[i]){sum+=c[i];}}
    init();
    for(int i=0;i<l.size();i++){
        int u=l[i].u,v=l[i].v;
        if(u>n&&!vis[u-n]) continue;
        if(_find(u)==_find(v)) continue;
        sum+=l[i].w;
        _union(u,v);
    }
    ans=min(ans,sum);
    return;
}
void dfs(int dep){
    if(dep>k){
        tree();
        return;
    }
    dfs(dep+1);
    vis[dep]=1;
    dfs(dep+1);
    vis[dep]=0;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);//这个要加 不加会爆
    cin>>n>>m>>k;
    init();
    for(int i=1;i<=m;i++){cin>>g[i].u>>g[i].v>>g[i].w;}
    sort(g+1,g+m+1,cmp);
    for(int i=1;i<=m;i++){//原图跑最小生成树
        int u=g[i].u,v=g[i].v;
        if(_find(u)==_find(v)) continue;
        _union(u,v);
        ans+=g[i].w;
        l.push_back(g[i]);
    }
    for(int j=1;j<=k;j++){//新边
        cin>>c[j];
        for(int i=1;i<=n;i++){
            int w;
            cin>>w;
            l.push_back({j+n,i,w});//村庄节点编号是n+j
        }
    }
    sort(l.begin(),l.end(),cmp);//提前排序
    dfs(1);
    cout<<ans;
    return 0;
}