Submission #6360242

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
#define N 200002
using namespace std;
struct edge{
	int u,v,w;
}e[N];
int n,q,i,f[N],num,fa[N];
int read()
{
	char c=getchar();
	int w=0;
	while(c<'0'||c>'9') c=getchar();
	while(c<='9'&&c>='0'){
		w=w*10+c-'0';
		c=getchar();
	}
	return w;
}
int my_comp(const edge &x,const edge &y)
{
	return x.w<y.w;
}
int find(int x)
{
	if(x!=fa[x]) fa[x]=find(fa[x]);
	return fa[x];
}
int Kruscal()
{
	for(int i=1;i<=n;i++) fa[i]=i;
	sort(e+1,e+num+1,my_comp);
	int cnt=n,ans=0;
	for(int i=1;i<=num;i++){
		int f1=find(e[i].u),f2=find(e[i].v);
		if(f1!=f2){
			fa[f1]=f2;
			cnt--;
			ans+=e[i].w;
		}
	}
	return ans;
}
signed main()
{
	memset(f,0x3f,sizeof(f));
	n=read();q=read();
	for(i=1;i<=q;i++){
		int a,b,c;
		a=read()+1;b=read()+1;c=read();
		e[++num]=(edge){a,b,c};
		f[a]=min(f[a],c+1);
		f[b]=min(f[b],c+2);
	}
	bool flag=0;
	for(i=1;i<=n;i++){
		f[i%n+1]=min(f[i]+2,f[i%n+1]);
		if(i==n&&!flag) i=0,flag=1;
	}
	for(i=1;i<=n;i++) e[++num]=(edge){i,i%n+1,f[i]};
	cout<<Kruscal()<<endl;
	return 0;
}

Submission Info

Judge Result