Lsz_2024111368 @ 2021-10-21 23:00:40
RT
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
struct bb
{
int to=-1;
int from=-1;
int lon=0;
int nex=-1;
}bian[200001];
struct kc
{
int last=-1;
int fir=-1;
int num=0;
}head[200001];
int p=0;
void lian(int a,int b,int c)
{
p++;
if(head[a].num)
{
bian[head[a].last].nex=p;
bian[p].from=a;
bian[p].to=b;
bian[p].lon=c;
head[a].num++;
head[a].last=p;
}
else
{
head[a].fir=p;
head[a].last=p;
head[a].num++;
bian[p].from=a;
bian[p].to=b;
bian[p].lon=c;
}
}
priority_queue<pair<int,int>>q;
int n;
int dis[100001]={};
bool use[100001]={};
int ans=0;
int cnt=0;
void prim()
{
q.push(make_pair(0,1));
for(int i=0;i<=n;i++)
{
dis[i]=9999999;
}
dis[1]=0;
while(!q.empty()&&cnt<n)
{
int ask=q.top().first;
int x=q.top().second;
q.pop();
if(use[x])
{
continue;
}
ans+=ask;
cnt++;
use[x]=1;
int f=head[x].fir;
for(int i=1;i<=head[x].num;i++)
{
if(dis[bian[f].to]>bian[f].lon)
{
dis[bian[f].to]=bian[f].lon;
q.push(make_pair(-dis[bian[f].to],bian[f].to));
}
f=bian[f].nex;
}
}
}
int main()
{
int m;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
lian(a,b,c);
lian(b,a,c);
}
prim();
if(cnt==n)
printf("%d",ans*(-1));
else
printf("orz");
return 0;
}
by Union_of_Britain @ 2021-10-21 23:05:14
@天下人间 日爆