Submission #2171844
Source Code Expand
#include<cstdio>
#include<algorithm>
int n,m,fa[200005],num;
long long ans,d[200005];
long long min(long long a,long long b){return a<b?a:b;}
struct node{int u,v;long long w;}e[400005];
int find(int u)
{
if(fa[u]==u)return u;
return fa[u]=find(fa[u]);
}
bool comp(node a,node b){return a.w<b.w;}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)d[i]=1e18;
for(int i=1;i<=m;i++)
{
int x,y;long long z;
scanf("%d%d%lld",&x,&y,&z);
e[++num]=(node){x,y,z};
d[x]=min(d[x],z+1);
d[y]=min(d[y],z+2);
}
for(int t=0;t<2;t++)
for(int i=0;i<n;i++)
d[(i+1)%n]=min(d[i]+2,d[(i+1)%n]);
for(int i=0;i<n;i++)e[++num]=(node){i,(i+1)%n,d[i]},fa[i]=i;
std::sort(e+1,e+1+num,comp);
int t=0;
for(int i=1;i<=num;i++)
if(find(e[i].u)!=find(e[i].v))
{
fa[fa[e[i].u]]=fa[e[i].v];
t++;ans+=e[i].w;if(t==n-1)break;
}
printf("%lld\n",ans);
}
Submission Info
Submission Time
2018-03-08 15:44:56+0900
Task
G - Zigzag MST
User
vjudge4
Language
C++14 (GCC 5.4.1)
Score
1300
Code Size
859 Byte
Status
AC
Exec Time
116 ms
Memory
9088 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:15: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:20:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld",&x,&y,&z);
^
Judge Result
Set Name
sample
all
Score / Max Score
0 / 0
1300 / 1300
Status
Set Name
Test Cases
sample
sample-01.txt, sample-02.txt, sample-03.txt
all
sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name
Status
Exec Time
Memory
01-01.txt
AC
1 ms
2176 KB
01-02.txt
AC
68 ms
6272 KB
01-03.txt
AC
105 ms
9088 KB
01-04.txt
AC
32 ms
8960 KB
01-05.txt
AC
21 ms
7808 KB
01-06.txt
AC
26 ms
8192 KB
01-07.txt
AC
22 ms
7040 KB
01-08.txt
AC
21 ms
6784 KB
01-09.txt
AC
26 ms
6784 KB
01-10.txt
AC
61 ms
8832 KB
01-11.txt
AC
90 ms
8320 KB
01-12.txt
AC
102 ms
8704 KB
01-13.txt
AC
103 ms
8704 KB
01-14.txt
AC
103 ms
8704 KB
01-15.txt
AC
106 ms
8704 KB
01-16.txt
AC
103 ms
8704 KB
01-17.txt
AC
102 ms
8704 KB
01-18.txt
AC
82 ms
8704 KB
01-19.txt
AC
21 ms
7040 KB
01-20.txt
AC
23 ms
6656 KB
01-21.txt
AC
45 ms
6656 KB
01-22.txt
AC
91 ms
8704 KB
01-23.txt
AC
93 ms
8704 KB
01-24.txt
AC
21 ms
6656 KB
01-25.txt
AC
116 ms
8704 KB
01-26.txt
AC
31 ms
6656 KB
01-27.txt
AC
29 ms
6656 KB
01-28.txt
AC
69 ms
8704 KB
01-29.txt
AC
88 ms
8448 KB
01-30.txt
AC
100 ms
8704 KB
sample-01.txt
AC
1 ms
2176 KB
sample-02.txt
AC
1 ms
2176 KB
sample-03.txt
AC
1 ms
2176 KB