记录编号	609202	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	4197.[CSP-S 2025 T2]道路修复(民间数据)	最终得分	100
用户昵称	hsl_beat	是否通过	通过
代码语言	C++	运行时间	10.798 s
提交时间	2025-11-02 23:12:11	内存使用	23.94 MiB

#include<bits/stdc++.h>
using namespace std;
#define int long long
int fa[1111111];
int n, m, k;
void init()
{
    for (int i = 1; i <= n + k; ++i) {
        fa[i] = i;
    }
}
int find(int x)
{
    if (fa[x] == x) {
        return x;
    }
    return fa[x] = find(fa[x]);
}
bool same(int x, int y)
{
    return find(x) == find(y);
}
void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    fa[x] = y;
}
struct node
{
    int u, v, w;
    bool operator<(const node& other) const {
        return w < other.w;
    }
};
vector<node> edges, eedges;
void solve()
{
    cin >> n >> m >> k;
    vector<int> c(k + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w; 
        edges.push_back({u, v, w});
    }
    init();
    sort(edges.begin(), edges.end(), [&](node a, node b) {
        return a.w < b.w;
    });
    int cnt = 0;
    for (int i = 0; i < m; ++i) {
        if (!same(edges[i].u, edges[i].v)) {
            merge(edges[i].u, edges[i].v); 
            cnt++;
            eedges.push_back(edges[i]);
        }
        if (cnt == n - 1) {
            break;
        }
    }
    edges = eedges;
    for (int i = 1; i <= k; ++i) {
        int x;
        cin >> x;
        c[i] = x; 
        for (int j = 1; j <= n; ++j) {
            int y;
            cin >> y;
            edges.push_back({n + i, j, y}); 
        }
    }
    sort(edges.begin(), edges.end(), [&](node a, node b) {
        return a.w < b.w;
    });
    int ans = LLONG_MAX;
    for (int i = 0; i < (1 << k); ++i) {
        init(); 
        int cnt1 = 0, cnt2 = 0;
        int cnt = 0; 
        for(int j = 1; j <= k; ++j) {
            if(i & (1 << (j - 1))) {
                cnt += c[j];
            }
        }
        for (int j = 0; j < edges.size(); ++j) {
            int u = edges[j].u;
            int v = edges[j].v;
            int w = edges[j].w;
            if (u > n && !((i >> (u - n - 1)) & 1)) {
                continue;
            }
            if (v > n && !((i >> (v - n - 1)) & 1)) { 
                continue;
            }
            if (!same(u, v)) {
                merge(u, v);
                cnt1++;
                cnt2 += w;
            }
            if (cnt1 == n + __builtin_popcount(i) - 1) {
                break;
            }
        }
        ans = min(ans, cnt2 + cnt); 
    }
    cout << ans << '\n';
}
signed main()
{
	freopen("road.in", "r", stdin);
	freopen("road.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    int T;
    T = 1;
    while (T--) {
        solve();
    }
    return 0;
}