prim+优先队列,最后一个点t掉了,求调
查看原帖
prim+优先队列,最后一个点t掉了,求调
553577
julihui325楼主2024/8/1 16:45
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
	int x=0;
	short f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}  

struct edge{
	int to,nxt,w;
}e[400010];
struct node{
	int id,dist;
	bool operator < (node x) const{
		return x.dist<dist;
	}
};
int head[200010],tot;
void add(int u,int v,int w){
	e[++tot].to=v;
	e[tot].nxt=head[u];
	e[tot].w=w;
	head[u]=tot;
}
int n,m,dis[5010];
bool vis[5010];
priority_queue <node> q;
int main(){
	int u,v,w,cnt=0,ans=0;
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		u=read();
		v=read();
		w=read();
		add(u,v,w);
		add(v,u,w);
	}
	for(int i=1;i<=n;i++)
		dis[i]=0x3f3f3f3f;
	q.push((node){1,0});
	while(!q.empty()||cnt<n-1){
		node t=q.top();
		q.pop();
		u=t.id;
		if(vis[u])
			continue;
		vis[u]=1;
		ans+=t.dist;
		cnt++;
		for(v=head[u];v;v=e[v].nxt){
			if(e[v].w<dis[e[v].to]){
				dis[e[v].to]=e[v].w;
				q.push((node){e[v].to,e[v].w});				
			}
		}
	}
	if(cnt<n-1)
		printf("orz");
	else
		cout<<ans;
	return 0;
}
2024/8/1 16:45
加载中...