Submission #2136331

---

Source Code Expand

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

const int N = 200005;
const int INF = 1e9 + 1e8;
typedef pair<int, int> ii;

int n, q;
int best[N];
int par[N];

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

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

long long res;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> q;
	for (int i = 0; i < n; ++i) best[i] = INF, par[i] = i;

	while(q--) {
		int u, v, w; cin >> u >> v >> w;
		ed.push_back({w, u, v});
		best[u] = min(best[u], w + 1);
		best[v] = min(best[v], w + 2);
	}

	priority_queue < ii, vector<ii>, greater<ii> > pq;
	for (int i = 0; i < n; ++i) if (best[i] != INF) {
		pq.push(make_pair(best[i], i));
	}

	while(!pq.empty()) {
		ii top = pq.top(); pq.pop();
		int u = top.second, best_u = top.first;
		if (best[u] != best_u) continue;

		if (best[(u + 1) % n] > best[u] + 2) {
			pq.push(ii(best[(u + 1) % n] = best[u] + 2, (u + 1) % n));
		}
	}

	for (int i = 0; i < n; ++i) {
		ed.push_back({best[i], i, (i + 1) % n});
	}

	sort(ed.begin(), ed.end());
	for (auto &e : ed) {
		if (anc(e.u) != anc(e.v)) {
			join(e.u, e.v);
			res += e.w;
		}
	}

	cout << res << endl;
}

Submission Info

Judge Result