灵异事件

4 4 2
1 4 6
2 3 7
4 2 5
4 3 4
1 1 8 2 4
100 1 3 2 4

4 4 1
1 4 6
2 3 7
4 2 5
4 3 4
1 1 8 2 4

#include <bits/stdc++.h>
using namespace std;
int ans=0;
int n,m,k;
int c[20],a[20][10010],efa[10010];
struct edge{
    int u,v,w;
};
bool cmp(edge a,edge b){
    return a.w<b.w;
}
int find(int x,int fa[]){
    if(fa[x]==x){
        return x;
    }
    return fa[x]=find(fa[x],fa);
}
vector<edge> edges,nedges;
int vis[20];
void kl(){
    int nans=0;
    int fa[10020];
    vector<edge> idge;
    for(int i=1;i<=n+k;i++){
        fa[i]=i;
    }
    for(int i=0;i<nedges.size();i++){
        idge.push_back({nedges[i].u,nedges[i].v,nedges[i].w});
    }
    for(int i=1;i<=k;i++){
        if(vis[i]){
            nans+=c[i];
            for(int j=1;j<=n;j++){
                idge.push_back({n+i,j,a[i][j]});
            }
        }
    }
    sort(idge.begin(),idge.end(),cmp);
    for(int i=0;i<idge.size();i++){
        int u=idge[i].u,v=idge[i].v,w=idge[i].w;
        u=find(u,fa),v=find(v,fa);
        if(v!=u){
            fa[v]=u;
            nans+=w;
        }
    }
    ans=min(ans,nans);
}
void dfs(int now){
    if(now==k+1){
        kl();
        return ;
    }
    dfs(now+1);
    vis[now]=1;
    dfs(now+1);
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        edges.push_back({u,v,w});
    }
    sort(edges.begin(),edges.end(),cmp);
    for(int i=1;i<=n;i++){
        efa[i]=i;
    }
    for(int i=0;i<edges.size();i++){
        int u=edges[i].u,v=edges[i].v,w=edges[i].w;
        u=find(u,efa),v=find(v,efa);
        if(u!=v){
            efa[v]=u;
            nedges.push_back({u,v,w});
            ans+=w;
        }
    }
    for(int i=1;i<=k;i++){
        cin>>c[i];
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    dfs(1);
    cout<<ans;
    return 0;
}