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;
}