考慮到對(duì)于 \(k\) 個(gè)鄉(xiāng)鎮(zhèn)明顯可以狀壓枚舉所有鄉(xiāng)鎮(zhèn)選擇的方案，然后暴力計(jì)算目前選擇的鄉(xiāng)鎮(zhèn)與 \(n\) 個(gè)城市的最小生成樹，此時(shí)邊數(shù)時(shí) \(O(kn+m)\) 級(jí)別的，那么時(shí)間復(fù)雜度是 \(O(2^k(kn+m)log\ (kn+m))\) 的，這樣必然會(huì)超時(shí)。我們于是考慮減少邊的個(gè)數(shù)，我們不難發(fā)現(xiàn)，在最開始只有 \(n\) 個(gè)城市時(shí)，\(m\) 條邊中不是最小生成樹的邊在加入了新的鄉(xiāng)鎮(zhèn)后必然也是對(duì)答案沒有貢獻(xiàn)的，所以我們可以不管這些無貢獻(xiàn)的邊，將每次求最小生成樹的邊數(shù)降到 \(O(kn)\) 級(jí)別的。但此時(shí)我們又發(fā)現(xiàn)如果每次求最小生成樹時(shí)對(duì)所有邊進(jìn)行排序，時(shí)間復(fù)雜度比較劣，我們可以考慮預(yù)處理出每個(gè)城鎮(zhèn)的 \(n\) 條邊的序列使其有序，這樣每次求最小生成樹時(shí)便可以使用歸并排序使排序復(fù)雜度更優(yōu)，此時(shí)時(shí)間復(fù)雜度是 \(O(2^kkn \alpha(n))\) 的。

#include<bits/stdc++.h>
using namespace std;
int n,m,k,f[10015],c[15]; 
struct node{
	int u,v,w;
}s[1000005],nw[10005],init[15][10005],t[2][120005];
long long ans=0;
int getf(int x){return (x==f[x])?x:f[x]=getf(f[x]);}
int main(){
	cin>>n>>m>>k;
	for(int i=0;i<m;i++)cin>>s[i].u>>s[i].v>>s[i].w;
	sort(s,s+m,[](node x,node y){return x.w<y.w;});
    int tmp=0,p=0;
    for(int i=1;i<=n;i++)f[i]=i;
    while(tmp<n-1){
        int fx=getf(s[p].u),fy=getf(s[p].v);
        if(fx!=fy){
            f[fx]=fy;
            ans+=s[p].w;
            tmp++;
            nw[tmp]=s[p];
        }
        p++;
    }
    for(int i=1;i<=k;i++){cin>>c[i];for(int j=1;j<=n;j++){cin>>init[i][j].w;init[i][j].u=n+i;init[i][j].v=j;}sort(init[i]+1,init[i]+1+n,[](node x,node y){return x.w<y.w;});}
    for(int i=1;i<(1<<k);i++){
        for(int j=1;j<=n+k;j++)f[j]=j;
        int sum=0,id=0;
        int num=n+__builtin_popcount(i),cnt=0,kk=1;
        long long anss=0;
        for(int j=1;j<n;j++)t[id][++sum]=nw[j];
        for(int j=1;j<=k;j++){
            if(!((1<<(j-1))&i))continue;
            anss+=c[j];
            id^=1;
            int l=1,r=1,summ=0;
            while(l<=sum&&r<=n){
                if(t[id^1][l].w<=init[j][r].w)t[id][++summ]=t[id^1][l++];
                else t[id][++summ]=init[j][r++];
            }
            while(l<=sum)t[id][++summ]=t[id^1][l++];
            while(r<=n)t[id][++summ]=init[j][r++];
            sum=summ;
        }
        while(cnt<num-1){
            int fx=getf(t[id][kk].u),fy=getf(t[id][kk].v);
            if(fx!=fy){
                f[fx]=fy;
                anss+=t[id][kk].w;
                cnt++;
            }
            kk++;
        }
        ans=min(ans,anss);
    }
    cout<<ans;
	return 0;
}