Submission #7940031

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define int long long
const int inf=2147483647;
il int read()
{
int x=0;int f=1;
char s=getchar();
while(s<'0' || s>'9')
{if(s=='-')f=-1;s=getchar();}
while(s>='0' && s<='9')
{x=x*10+s-'0';s=getchar();
}
return x*f;		
}

struct Edge
{int u,v,w;}edge[2001000];
int head[2001000],tot;
//void add(int x,int y,int w){
  //  ed[++tot].nxt=head[x];
	//ed[tot].to=y;
	///./ed[tot].w=w;
	//head[x]
int Min_value[2001000];
int fa[555000],n,q,ans,eu,ev,cnt;

il bool cmp(Edge a,Edge b)
{return a.w<b.w;}

il int Union(int x)
{while(x!=fa[x])x=fa[x]=fa[fa[x]];
return x;}

il void kruscal()
{
sort (edge+1,edge+1+cnt,cmp);
for(int i=1;i<=cnt;i++)
{int ttt=0;
int eu=Union(edge[i].u);
int ev=Union(edge[i].v);
if(eu==ev){continue;}
	ans+=edge[i].w;
	fa[eu]=ev;++ttt; 
	if(ttt==n-1)
	{break;}}}
signed main()
{
	n=read();
	q=read();
    memset(Min_value,0x3f,sizeof(Min_value));
    while(q--)
    {
        int u=read()+1;int v=read()+1;int w=read();
        edge[++cnt]=(Edge){u,v,w};
        Min_value[u]=min(Min_value[u],w+1);
        Min_value[v]=min(Min_value[v],w+2);
    }
	for(int i=1;i<=n;i++)
	{fa[i]=i;}
	for(int i=1;i<=n;i++){
		Min_value[i%n+1]=min(Min_value[i%n+1],Min_value[i]+2);
	}
	for(int i=1;i<=n;i++){
		Min_value[i%n+1]=min(Min_value[i%n+1],Min_value[i]+2);
	}
	for(int i=1;i<=n;i++){
		edge[++cnt]=(Edge){i,i%n+1,Min_value[i]};
	}
kruscal();
cout<<ans;
return 0;
}

Submission Info

Judge Result