Submission #2168836
Source Code Expand
#include<cstdio> #include<algorithm> #include<cstring> #define ll long long struct r{ int u,v,w; }e[400050]; int w[200050],fa[200050],cnt,n,m; ll ans; int get_fa(int u){return fa[u]==u ? u:fa[u]=get_fa(fa[u]);} bool cmp(r a,r b){return a.w<b.w;} int main(){ scanf("%d%d",&n,&m); memset(w,127,sizeof w); for (int i=1;i<=m;i++){ scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); w[e[i].u]=std::min(w[e[i].u],e[i].w+1); w[e[i].v]=std::min(w[e[i].v],e[i].w+2); } for (int i=0;i<n;i++) fa[i]=i; for (int i=1;i<(n<<1);i++) w[i]=std::min(w[i],w[i-1]+2); for (int i=0;i<n;i++) e[++m]=(r){i,(i+1)%n,std::min(w[i],w[i+n])}; std::sort(e+1,e+m+1,cmp); for (int i=1;i<=m;i++){ if ((u=get_fa(e[i].u))==(v=get_fa(e[i].v))) continue; fa[v]=u; ans+=1ll*e[i].w; cnt++; if (cnt==n-1) { printf("%lld",ans); return 0; } } }
Submission Info
Submission Time | |
---|---|
Task | G - Zigzag MST |
User | vjudge4 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 834 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:27:8: error: ‘u’ was not declared in this scope if ((u=get_fa(e[i].u))==(v=get_fa(e[i].v))) continue; ^ ./Main.cpp:27:28: error: ‘v’ was not declared in this scope if ((u=get_fa(e[i].u))==(v=get_fa(e[i].v))) continue; ^ ./Main.cpp:28:6: error: ‘v’ was not declared in this scope fa[v]=u; ^ ./Main.cpp:28:9: error: ‘u’ was not declared in this scope fa[v]=u; ^ ./Main.cpp:13:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&n,&m); ^ ./Main.cpp:16:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); ^