Submission #6355865

---

Source Code Expand

/*
  mail: mleautomaton@foxmail.com
  author: MLEAutoMaton
  This Code is made by MLEAutoMaton
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi(){
	int f=1,sum=0;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
const int N=400010;
struct node{int u,v,w;}e[N<<1];
bool operator<(node a,node b){return a.w<b.w;}
int f[N];
int find(int x){if(f[x]!=x)f[x]=find(f[x]);return f[x];}
int a[N],n,m,cnt;
int main(){
	n=gi();m=gi();memset(a,63,sizeof(a));
	for(int i=1;i<=m;i++){
		int x=gi()+1,y=gi()+1,z=gi();
		a[x]=min(a[x],z+1);
		a[y]=min(a[y],z+2);
		e[++cnt]=(node){x,y,z};
	}
	for(int i=1;i<=n;i++)a[i]=min(a[i],a[(i-2+n)%n+1]+2);
	for(int i=1;i<=n;i++)a[i]=min(a[i],a[(i-2+n)%n+1]+2);	
	for(int i=1;i<n;i++)e[++cnt]=(node){i,i+1,a[i]};
	e[++cnt]=(node){n,1,a[n]};
	sort(e+1,e+cnt+1);for(int i=1;i<=n;i++)f[i]=i;
	ll ans=0;
	for(int i=1;i<=cnt;i++){
		int u=find(e[i].u),v=find(e[i].v);
		if(u!=v){
			ans+=e[i].w;
			f[v]=u;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Submission Info

Judge Result