Submission #1863873

---

Source Code Expand

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

const int N = 100005;

struct Edge {
	int u, v, w;

	Edge (int u, int v, int w) :
		u(u), v(v), w(w) {} 

	bool operator < (const Edge& rhs) const {
		return w < rhs.w;
	}
};

int n, m, k;
int color[N];
int par[N * 2];
vector<Edge> E;

int find(int u) {
	return (u == par[u]) ? u : par[u] = find(par[u]);
}

bool join(int u, int v) {
	u = find(u), v = find(v), par[u] = v; return (u != v);
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; ++i) cin >> color[i];
	for (int i = 1; i <= m; ++i) {
		int u, v, w; cin >> u >> v >> w;
		E.push_back(Edge(u, v, w));
	}
	sort(E.begin(), E.end());
	for (int i = 1; i <= n + k; ++i) par[i] = i;
	int cnt = k - 1;
	long long res = 0;
	for (int i = 0; i < m; ++i) {
		int u = E[i].u, v = E[i].v, w = E[i].w;
		if (color[u]) u = color[u] + n;
		if (color[v]) v = color[v] + n;
		if (!join(u, v)) continue;
		res += w, cnt--;
		if (!cnt) break;
	}
	if (cnt) cout << -1;
	else cout << res;
}

Submission Info

Judge Result