Submission #2864196

---

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;
}
//rt

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:33:24: 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:33: 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