Submission #4419533

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define Set(a,b) memset(a,b,sizeof(a))
template<class T>inline void init(T&x){
	x=0;char ch=getchar();bool t=0;
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
	if(t) x=-x;return;
}
typedef long long ll;
int n,m;
const int N=5e5+10;
struct edge{
	int u,v;ll val;
	inline bool operator <(const edge B)const{return val<B.val;}
}a[N];int cnt=0;
int q,fa[N];
int find(int x){return fa[x]==x? x:fa[x]=find(fa[x]);}
ll data[N];
int main()
{
	init(n),init(q);Set(data,-1);
	if(n==1) return puts("0"),0;
	for(int i=1;i<=q;++i){
		int X,Y;ll Z;
		init(X),init(Y),init(Z);
		a[++cnt]=(edge){X,Y,Z};
		if(~data[X]) data[X]=min(data[X],Z+1);
		else data[X]=Z+1;
		if(~data[Y]) data[Y]=min(data[Y],Z+2);
		else data[Y]=Z+2;
	}
	int pos=-1;
	for(int i=0;i<n;++i) {if(~data[i]) {if((~pos)&&data[pos]>data[i])pos=i;else if(pos==-1) pos=i;}}
	int u=pos,v;
	for(int i=1;i<=n;u=v,++i) {
		v=u+1;if(v>=n) v-=n;
		if(data[u]==-1) continue;
		if(~data[v]) data[v]=min(data[v],data[u]+2);
		else data[v]=data[u]+2;
		if(~data[u]) a[++cnt]=(edge){u,v,data[u]};
	}
	sort(a+1,a+1+cnt);
	for(int i=0;i<n;++i) fa[i]=i;
	ll tot=0;
	for(int i=1;i<=cnt;++i) {
		u=a[i].u,v=a[i].v;
		int fx=find(u),fy=find(v);
		if(fx==fy) continue;
		else fa[fx]=fy,tot+=a[i].val;
	}
	cout<<tot<<endl;
	return 0;
}

Submission Info

Judge Result