VxiaohuanV @ 2021-11-17 19:31:00
#include <bits/stdc++.h>
using namespace std;
#define ri register int
#define M 5005
struct edge{
int v,val;
edge(){}
edge(int a,int b){v=a,val=b;}
};
vector <edge> p[M];
int n,m;
long long dis[M];
int val[M],vis[M];
struct cmp{
bool operator ()(const int a,const int b)const
{
return val[a]>val[b];
}
};
priority_queue <int,vector<int>,cmp> q;
long long ans;
bool flag;
int cent;
void dj()
{
memset(val,0x3f,sizeof(val));
memset(dis,0x3f,sizeof(dis));
dis[1]=0;val[1]=0;
q.push(1);
while(n--)
{
cent++;
int a=1; // attention
while(!q.empty())
{
a=q.top();
if(vis[a]) q.pop();
else break;
}
if(vis[a])
{
flag=1;break;
};
vis[a]=1;
ans+=val[a];
for(ri i=0;i<p[a].size();i++)
{
int b=p[a][i].v;
if(vis[b]) continue;
if(val[b]>p[a][i].val)
{
val[b]=p[a][i].val;q.push(b);
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(ri i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
edge t=edge(b,c);
p[a].push_back(t);
t=edge(a,c);
p[b].push_back(t);
}
dj();
if(flag) printf("orz");
else
printf("%lld",ans);
return 0;
}
by XiaoQuQu @ 2021-11-19 10:00:17
@VxiaohuanV 额没看懂您的代码