Submission #4419161

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
inline int read()
{
	int sum=0,p=1;char ch=getchar();
	while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();
	if(ch=='-')p=-1,ch=getchar();
	while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();
	return sum*p;
}

const int maxn=2e5+20;
const int inf=0x3f3f3f3f;

struct Edge {
	int u,v,w;
};
Edge E[maxn<<1];
int m;

int f[maxn];

int n,q;

inline void init()
{
	n=read();q=read();
	memset(f,inf,sizeof(f));
	REP(i,1,q)
	{
		int u=read(),v=read(),c=read();
		E[++m]=(Edge){u,v,c};
		chkmin(f[u],c+1);
		chkmin(f[v],c+2);
	}
	REP(i,0,n-1)chkmin(f[i+1<n?i+1:0],f[i]+2);
	REP(i,0,n-1)chkmin(f[i+1<n?i+1:0],f[i]+2);
	REP(i,0,n-1)E[++m]=(Edge){i,i+1<n?i+1:0,f[i]};
}

inline bool cmp(Edge a,Edge b){ return a.w<b.w;}
int fa[maxn];
int fin(int x){ return x==fa[x]?x:fa[x]=fin(fa[x]);}
inline void merge(int x,int y){ x=fin(x);y=fin(y); fa[y]=x;}

inline void doing()
{
	REP(i,1,n)fa[i]=i;
	sort(E+1,E+m+1,cmp);
	ll ans=0;
	REP(i,1,m)
	{
		int u=E[i].u,v=E[i].v;
		if(fin(u)==fin(v))continue;
		merge(u,v);
		ans+=E[i].w;
	}
	printf("%lld\n",ans);
}

int main()
{
	init();
	doing();
	return 0;
}

Submission Info

Judge Result