Submission #6133601

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200200;
int u[maxn], to[maxn];
long long best[maxn];
void init(){ 
	for(int i = 0; i < maxn; i++){
		u[i] = i;
		to[i] = -1;
		best[i] = 1ll<<60;
	}
}
int find(int x){
	if(x == u[x]) return x;
	return u[x] = find(u[x]);
}
long long cost[maxn];
vector<pair<int,int> > e[maxn];
int main(){
	int n, q; cin >> n >> q;
	for(int i = 0; i < n; i++) cost[i] = 1ll<<60;
	for(int i = 0; i < q; i++){
		int a, b; long long c; cin >> a >> b >> c;
		cost[a] = min(cost[a], c + 1);
		cost[b] = min(cost[b], c + 2);
		e[a].push_back({b, c});
		e[b].push_back({a, c});
	}
	for(int i = 0; i < 2 * n; i++){
		int now = i % n; 
		int prv = now - 1; if(prv < 0) prv += n;
		cost[now] = min(cost[now], cost[prv] + 2);
	}
	auto dist = [&](int u, int v){
		if(u == v) return 0ll;
		long long ans = 1ll<<60;
		for(int rot = 0; rot < 2; rot++){
			swap(u, v);
			if(u < v){
				ans = min(ans, cost[u] + (v - u - 1) * 2);
				ans = min(ans, cost[v] + (n - v + u - 1) * 2);
			}
		}		
		return ans;
	};
	init();
	set<int> all;
	for(int i = 0; i < n; i++){
		all.insert(i);
	}
	int comps = n;
	long long ans = 0;
	while(comps > 1){
		vector<pair<int,int> > vert;
		for(int i = 0; i < n; i++){
			vert.push_back({find(i), i});
			to[find(i)] = -1;
			best[find(i)] = 1ll<<60;
		}
		sort(vert.begin(), vert.end());
		int j = 0;
		for(int i = 0; i < n; i = j){
			while(j < n && vert[j].first == vert[i].first) j++;
			for(int k = i; k < j; k++) all.erase(vert[k].second);
			int head = vert[i].first;
			for(int k = i; k < j; k++){
				auto it = all.lower_bound(vert[k].second);
				int going;
				if(it == all.end()) going = *all.begin();
				else going = *it;
				long long d = dist(vert[k].second, going);
				int hgo = find(going);
				if(best[head] > d) best[head] = d, to[head] = going;
				if(best[hgo] > d) best[hgo] = d, to[hgo] = head;
			}
			for(int k = i; k < j; k++) all.insert(vert[k].second);
		}
		for(int i = 0; i < n; i++){
			int head = find(i);
			for(auto ed : e[i]){
				if(find(ed.first) != head){
					if(best[head] > ed.second){
						best[head] = ed.second;
						to[head] = ed.first;
					}
					if(best[find(ed.first)] > ed.second){
						best[find(ed.first)] = ed.second;
						to[find(ed.first)] = head;
					}
				}
			}
		}
		vector<pair<long long, int>> heads;
		for(int i = 0; i < n; i++) if(i == find(i)) heads.push_back({best[i], i});
		sort(heads.begin(), heads.end());
		for(auto h : heads){
			int head = h.second;
			if(find(head) != find(to[head])){
				ans += best[head];
				comps--;
				u[find(head)] = find(to[head]);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result