Submission #4419160

---

Source Code Expand

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gt getchar()
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
typedef std::pair<int,int> P;
#define mk std::make_pair
#define fr first
#define sc second
inline int in()
{
	int k=0;char ch=gt;bool p=1;
	while(ch<'-')ch=gt;if(ch=='-')ch=gt,p=0;
	while(ch>'-')k=k*10+ch-'0',ch=gt;
	return p?k:-k;
}
const int N=2e5+5;
int f[N],fa[N];
struct node{int u,v,w;}E[N<<2];
inline bool operator<(const node &a,const node &b){return a.w<b.w;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main()
{
	int n=in(),Q=in(),tot=Q;
	memset(f,0x3f,n<<2);
	for(int i=1;i<=Q;++i)
	{
		int u=in(),v=in(),w=in();
		E[i]=(node){u,v,w};
		f[u]=std::min(f[u],w+1);
		f[v]=std::min(f[v],w+2);
	}
	for(int i=1;i<n;++i)f[i]=std::min(f[i],f[i-1]+2);
	f[0]=std::min(f[0],f[n-1]+2);
	for(int i=1;i<n;++i)f[i]=std::min(f[i],f[i-1]+2);
	for(int i=0;i<n-1;++i)E[++tot]=(node){i,i+1,f[i]};
	E[++tot]=(node){n-1,0,f[n-1]};
	std::sort(E+1,E+tot+1);
	ll mst=0;int cnt=1;
	for(int i=1;i<=n;++i)fa[i]=i;
	for(int i=1;i<=tot&&cnt<n;++i)
	{
		int u=find(E[i].u),v=find(E[i].v);
		if(u==v)continue;++cnt;fa[u]=v;mst+=E[i].w;
	}
	printf("%lld\n",mst);
	return 0;
}

Submission Info

Judge Result