Submission #53121634

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

struct DSU
{
    vector<int> rt;
    DSU(int n) : rt(n)
    {
        iota(rt.begin(), rt.end(), 0);
    }
    int find(int u)
    {
        if (u == rt[u])
        {
            return u;
        }
        return rt[u] = find(rt[u]);
    }
    bool same(int u, int v)
    {
        return find(u) == find(v);
    }
    void unite(int u, int v)
    {
        u = find(u), v = find(v);
        rt[u] = v;
    }
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<pair<int, vector<int>>> ed(m);
    for (int i = 0; i < m; i++)
    {
        int M, w;
        cin >> M >> w;
        vector<int> res(M);
        for (int j = 0; j < M; j++)
        {
            cin >> res[j];
            res[j]--;
        }
        ed[i] = make_pair(w, res);
    }
    int cnt = 0;
    long long ans = 0;
    DSU dsu(n);
    sort(ed.begin(), ed.end());
    for (auto &[w, res] : ed)
    {
        int M = res.size();
        for (int i = 1; i < M; i++)
        {
            if (!dsu.same(res[i - 1], res[i]))
            {
                ans += w;
                dsu.unite(res[i - 1], res[i]);
                cnt++;
            }
        }
    }
    cout << (cnt == n - 1 ? ans : -1) << '\n';
    return 0;
}

Submission Info

Judge Result