90分代码求调
  • 板块灌水区
  • 楼主MarsNotFound
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/4/16 14:08
  • 上次更新2024/4/16 18:29:48
查看原帖
90分代码求调
973789
MarsNotFound楼主2024/4/16 14:08

不知道为什么WA了#7

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
struct data
{
	int dis,x;
	bool operator<(data a)const{return dis>a.dis;}
};
int ne[maxn<<1],e[maxn<<1],w[maxn<<1],head[maxn],idx;
int n,m,k,u1,v1,w1,ans,cnt,flag;
bool vis[maxn];
void add(int a,int b,int c)
{
	e[++idx]=b;
	ne[idx]=head[a];
	head[a]=idx;
	w[idx]=c;
}
void Prim()
{
	priority_queue<data>q;
	q.push((data){0,1});
	while(!q.empty())
	{
		data u=q.top();
		ans+=u.dis;
		cnt++;
		if(n-cnt+1==k)
		{
			flag=1;
			break;
		}
		if(vis[u.x])continue;
		vis[u.x]=true;
		q.pop();
		for(int i=head[u.x];i!=-1;i=ne[i])
		{
			if(!vis[e[i]])q.push((data){w[i],e[i]});
		}
		while(!q.empty() && vis[q.top().x])
			q.pop();
	}
}
int main()
{
	memset(head,-1,sizeof(head));
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		cin>>u1>>v1>>w1;
		add(u1,v1,w1);
		add(v1,u1,w1);
	}
	Prim();
	if(!flag)cout<<"No Answer";
	else cout<<ans;
	
	return 0;
}

题目

2024/4/16 14:08
加载中...