Submission #3435769

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
	int x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
	return x*f;
}
inline ll readll(){
	ll x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
	return x*f;
}
const int maxn=2e5+10,inf=0x3f3f3f3f;
int n,m,Min[maxn],fa[maxn];
struct Edge{
	int x,y,z;
	bool operator <(const Edge &rhs) const{
		return z<rhs.z;
	}
}E[maxn<<1];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
int main(){
	memset(Min,inf,sizeof(Min));
	n=read(),m=read();
	REP(i,1,m){
		E[i].x=read(),E[i].y=read(),E[i].z=read();
		chkmin(Min[E[i].x],E[i].z+1);
		chkmin(Min[E[i].y],E[i].z+2);
	}
	int cur=inf;
	REP(i,0,2*n){
		cur+=2;
		chkmin(Min[i%n],cur);
		chkmin(cur,Min[i%n]);
	}
	REP(i,0,n-1) E[++m]=(Edge){i,(i+1)%n,Min[i]};
	sort(E+1,E+m+1);
	REP(i,0,n-1) fa[i]=i;
	ll ans=0;
	REP(i,1,m){
		int x=E[i].x,y=E[i].y,z=E[i].z;
		if(find(x)==find(y)) continue;
		fa[find(x)]=find(y);
		ans+=z;
	}
	printf("%lld\n",ans);
	return 0;
}

Submission Info

Judge Result