Submission #5017727

---

Source Code Expand

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second

using std::cin;
using std::cout;
using LL = long long;
using pii = std::pair<int, int>;
using pip = std::pair<int, pii>;
const int MAXN = 2e5 + 10;

int f[MAXN];

int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }

bool unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy)return false;
    f[fx] = fy;
    return true;
}

void solve() {
    int n, m;
    cin >> n >> m;
    std::priority_queue<pip, std::vector<pip>, std::greater<>> q;
    for (int i = 1; i <= n; ++i) f[i] = i;

    for (int i = 0, A, B, C; i < m; ++i) {
        cin >> A >> B >> C;
        q.push({C, {A, B}});
    }

    int cnt = 0;
    LL ans = 0;
    std::set<pii> S;
    while (cnt != n - 1) {
        pip p = q.top();
        q.pop();
        int c = p.fi, a = p.se.fi, b = p.se.se;
        // cout << a << " " << b <<"\n";
        if (S.find({a, b}) != end(S)) continue;
        S.insert({a, b});
        if (unite(a, b)) ans += c, cnt++;
        q.push({c + 1, {b, (a + 1) % n}});
    }
    cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef trote
    freopen("../1.txt", "r", stdin);
    freopen("../out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

Submission Info

Judge Result