求救!! prim 44分 找不出哪里错了 , qwq 5555
查看原帖
求救!! prim 44分 找不出哪里错了 , qwq 5555
267778
sfksf楼主2021/11/17 19:31
#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;
}
 
2021/11/17 19:31
加载中...