CHEER - Động viên đàn bò

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
#define ii pair<int, int>
#define iii pair<int, ii>
#define X first
#define Y second
const int N = 10100;
const int M = 100010;
using namespace std;
int lab[N], C[N];
iii e[M];
int n, m;

int root(int u) 
    {return (lab[u] <= 0) ? u : (lab[u] = root(lab[u]));}
void unite(int u, int v) 
    {if (lab[u] > lab[v]) swap(u, v); if (lab[u] == lab[v]) lab[u]--; lab[v] = u;}

int main() {
    ios :: sync_with_stdio(0); cin.tie();
    cin >> n >> m;
    int u, v, L;
    for(int i = 1; i <= n; i++) cin >> C[i];
    for(int i = 1; i <= m; i++) {
        cin >> u >> v >> L;
        e[i] = iii(C[u] + C[v] + L + L, ii(u, v));
    }
    sort(e + 1, e + 1 + m);
    int cnt = 0, res = *min_element(C + 1, C + 1 + n);
    for(int i = 1; i <= m; i++) {
        u = root(e[i].Y.X); 
        v = root(e[i].Y.Y);
        if (u != v) {
            res += e[i].X;
            unite(u, v);
            cnt++;
        }
        if (cnt == n - 1) break;
    }
    cout << res << endl;
    return 0;
}

Download