백준 1185번 : 유럽 여행 - MST, Kruskal

https://www.acmicpc.net/problem/1185

1185번: 유럽여행

#include <bits/stdc++.h>

#define MX 10001
using namespace std;

int N, P;

struct Edge {
    int from, to, weight;

    bool operator<(const Edge &b) const {
        return weight < b.weight;
    }
};

int countryCost[MX], unf[MX];
vector<Edge> realEdges;

int Find(int a) {
    if (unf[a] < 0) {
        return a;
    }
    return unf[a] = Find(unf[a]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);

    if (a == b) return;
    if (unf[a] > unf[b]) {
        unf[b] += unf[a];
        unf[a] = b;
    } else {
        unf[a] += unf[b];
        unf[b] = a;
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> P;

    memset(unf, -1, sizeof(unf));

    int minCountry = 1e9;
    for (int i = 1; i <= N; i++) {
        cin >> countryCost[i];
        minCountry = min(minCountry, countryCost[i]);
    }

    for (int i = 1; i <= P; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        realEdges.push_back({a, b, 2 * c + countryCost[a] + countryCost[b]});
    }

    sort(realEdges.begin(), realEdges.end());

    int ans = 0;

    for (auto edge: realEdges) {
        auto [a, b, c] = edge;
        int aa = Find(a);
        int bb = Find(b);

        if (aa != bb) {
            Union(aa, bb);
            ans += c;
        }
    }


    cout << ans + minCountry << '\n';

    return 0;
}