Submission #3496307

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <algorithm>
using std::sort;
using std::min;
const int MAXN=400010;
const int INF=2e9;
struct Edge {
	int u,v,w;
	friend bool operator<(Edge a,Edge b) {
		return a.w<b.w;
	}
}ed[MAXN];
int cnt=0;
inline void join(int x,int y,int z) {
	ed[++cnt].u=x;
	ed[cnt].v=y;
	ed[cnt].w=z;
	return;
}
int f[MAXN];
inline void init(int n) {
	for(int i=0;i<=n;++i) {
		f[i]=i;
	}
}
int find(int x) {
	return x==f[x]?x:(f[x]=find(f[x]));
}
int best[MAXN];
int main() {
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i=0;i<=n;++i) {
		best[i]=INF;
	}
	int x,y,z;
	for(int i=1;i<=q;++i) {
		scanf("%d%d%d",&x,&y,&z);
		join(x,y,z);
		best[x]=min(best[x],z+1);
		best[y]=min(best[y],z+2);
	}	
	for(int i=0;i<n*2;++i) {
		best[(i+1)%n]=min(best[(i+1)%n],best[i%n]+2); //n*2防止更新了n-1到0 
	}
	for(int i=0;i<n;++i) {
		if(best[i]!=INF) join(i,(i+1)%n,best[i]);
	}
	init(n);
	sort(ed+1,ed+1+cnt);
	long long ans=0;
	for(int i=1;i<=cnt;++i) {
		int a=find(ed[i].u),b=find(ed[i].v);
		if(a!=b) {
			ans+=ed[i].w;
			f[a]=b;
		}
	}
	printf("%lld",ans);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:33:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&q);
                     ^
./Main.cpp:39:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&x,&y,&z);
                           ^

Judge Result