Noic - Avançado - Semana 55 - Problema 2

noic-avancado-s55-p2.cpp

// Noic - Avançado - Semana 55 - Problema 2
// O(M log M)

#include <bits/stdc++.h>

using namespace std;

const int maxn = 4e5+10;
const long long inf = 1e18+10;

typedef long long ll;

struct E
{
    int x, y;
    ll d;
} aresta[maxn];

int pai[maxn], peso[maxn];

ll a[maxn];

// inicia o Union-Find para o Kruskal
void Init(int n)
{
    for (int i = 1; i <= n; i++)
        pai[i] = i, peso[i] = 1;
}

// funções do Union-Find
int Find(int x)
{
    if (pai[x] == x) return x;
    return pai[x] = Find(pai[x]);
}

void Join(int x, int y)
{
    x = Find(x), y = Find(y);
    if (x == y) return;

    if (peso[x] < peso[y]) swap(x, y);
    pai[y] = x, peso[x] += peso[y];
}

// comparador para ordenar as arestas pelos seus pesos
bool comp(E a, E b)
{
    return a.d < b.d;
}

int main(void)
{
    int n, k;
    scanf("%d %d", &n, &k);

    int V;
    ll menor = inf;

    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);

        if (a[i] < menor) 
            menor = a[i], V = i;
    }

    int aux = 0;

    // insere todas as arestas de V para outro vértice
    for (int i = 1; i <= n; i++)
        if (i != V)
            aresta[++aux] = {V, i, menor + a[i]};

    // arestas especiais
    for (int i = 1; i <= k; i++)
    {
        int u, v;
        ll w;
        
        scanf("%d %d %lld", &u, &v, &w);

        aresta[++aux] = {u, v, w};
    }

    sort(aresta+1, aresta+aux+1, comp);

    Init(n);

    // menor custo
    ll ans = 0LL;

    for (int i = 1; i <= aux; i++)
    {
        if (Find(aresta[i].x) != Find(aresta[i].y))
        {
            ans += aresta[i].d;
            Join(aresta[i].x, aresta[i].y);
        }
    }

    printf("%lld\n", ans);
}