Submission #3230593

---

Source Code Expand

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

const int RLEN=1<<18|1;
inline char nc() {
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob) ? -1 : *ib++;
}
inline int rd() {
	char ch=nc(); int i=0,f=1;
	while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();}
	while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();}
	return i*f;
}

const int N=4e5+50;
int n,q,mn[N],anc[N];
long long ans;

struct data {
	int x,y,w;
	data(int x,int y,int w) : x(x),y(y),w(w) {}
	friend inline bool operator <(const data &a,const data &b) {return a.w<b.w;}
};
vector <data> edge;

inline int ga(int x) {while(x!=anc[x]) x=anc[x]=anc[anc[x]];
}
int main() {
	n=rd(), q=rd();
	for(int i=0;i<2*n;i++) mn[i]=0x3f3f3f3f;
	for(int i=1;i<=q;i++) {
		int x=rd(), y=rd(), w=rd();
		mn[x]=min(mn[x],w+1);
		mn[y]=min(mn[y],w+2);
		edge.push_back(data(x,y,w));
	}
	for(int i=1;i<2*n;i++) mn[i]=min(mn[i],mn[i-1]+2);
	for(int i=0;i<=n-1;i++) {
		int w=min(mn[i],mn[i+n]);
		int x=i%n, y=(i+1)%n;
		edge.push_back(data(x,y,w));
	} sort(edge.begin(),edge.end());
	for(int i=0;i<n;i++) anc[i]=i;
	for(auto v:edge) {
		int x=ga(v.x), y=ga(v.y);
		if(x==y) continue;
		ans+=v.w; anc[x]=y; 
	} cout<<ans<<'\n';
}

Submission Info

Judge Result