Submission #2192275

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;

struct edge {
	int w; int u; int v;
	bool operator < (const edge &other) const {
		return w < other.w;
	}
};
vector <edge> ed;

int n, m, ncolor;
int c[N];
int par[N];
long long res;

// DSU
int anc(int p) { return p == par[p] ? p : par[p] = anc(par[p]); }
void join(int p, int q) { par[p] = q; } // p = anc(p), q = anc(q)

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> m >> ncolor;

	int more = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> c[i];
		if (!c[i]) ++more, c[i] = ncolor + more;
	}

	while(m--) {
		int u, v, w; cin >> u >> v >> w;
		ed.push_back({w, c[u], c[v]});
	}

	int tot = ncolor + more;

	for (int i = 1; i <= tot; ++i) par[i] = i;
	sort(ed.begin(), ed.end());

	int need = ncolor - 1;
	for (auto &e : ed) {
		int u = anc(e.u);
		int v = anc(e.v);
		if (u == v) continue;

		--need;
		join(u, v);
		res += e.w;

		if (!need) break;
	}

	if (!need) cout << res << endl;
	else cout << -1 << endl;
}

Submission Info

Judge Result