提出 #53110200

---

ソースコード 拡げる

#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <string>

#include <cmath>
#include <queue>
#include <stack>

#include <unordered_set>
#include <unordered_map>
#include <array>
#include <iomanip>

#include <atcoder/all>

using namespace std;

#define LL long long

inline int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') {
            f = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

inline void write(int x) {
	if (x < 0) {
		putchar('-'); x = -x;
	}
    static int sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48); 
}

inline void writeln(int x) {
	if (x < 0) {
		putchar('-'); x = -x;
	}
    static int sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48); 
	putchar('\n');
}

inline LL readll() {
    LL x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') {
            f = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

inline void writell(LL x) {
	if (x < 0) {
		putchar('-'); x = -x;
	}
    static LL sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48); 
}

inline void writellln(LL x) {
	if (x < 0) {
		putchar('-'); x = -x;
	}
    static LL sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48); 
	putchar('\n');
}
template<class DataType1, class DataType2>
void write(pair<DataType1, DataType2> a, char endSplit = ' ') {
    cout << "(" << a.first << ", " << a.second << ")" << endSplit;
}
template<class DataType>
void write(vector<DataType> &a, char split = ' ', char endSplit = '\n') {
    for (int i = 0; i < a.size(); ++i) {
        cout << a[i] << split;
    }
    cout << endSplit;
}

using mint = atcoder::modint998244353;

vector<int> f;

int gf(int u) {
    return f[u] == u ? u : f[u] = gf(f[u]);
}
void combine(int u, int v) {
    f[gf(u)] = gf(v);
}

class SubGraph {
public:
    int k;
    LL c;
    vector<int> a;

    void input() {
        k = read();
        c = readll();
        a = vector<int>(k);
        for (int i = 0; i < k; ++i) {
            a[i] = read() - 1;
        }
    
    }
};

bool cmp(const SubGraph &a, const SubGraph &b) {
    return a.c < b.c;
}

int main() {
	// std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    int n = read(), m = read();
    f = vector<int>(n);
    for (int i = 0; i < n; ++i) {
        f[i] = i;
    }

    vector<SubGraph> g(m);
    for (int i = 0; i < m; ++i) {
        g[i].input();
    }

    sort(g.begin(), g.end(), cmp);
    LL ans = 0;
    int cnt = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 1; j < g[i].k; ++j) {
            if (gf(g[i].a[j]) != gf(g[i].a[0])) {
                combine(g[i].a[j], g[i].a[0]);
                ans += g[i].c;
                ++cnt;
            }
        }
    }

    if (cnt == n - 1) {
        writellln(ans);
    } else {
        writellln(-1);
    }

	return 0;
}

提出情報

ジャッジ結果