prim编译不过
查看原帖
prim编译不过
670998
Neven楼主2023/7/31 15:49
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, head[N], cnt, ans, sum, u, v, w, dis[N], vis[N];
struct node{
	int to, next, w;
}e[N];
struct prim_node{
	int u, dis;
};
priority_queue<prim_node, vector<prim_node>, greater<prim_node> >q;
void add(int u, int v, int w){
	e[++cnt].to = v;
	e[cnt].w = w;
	e[cnt].next = head[u];
	head[u] = cnt;
}
void prim(){
	dis[1] = 0;
	q.push({1, dis[1]});
	while(!q.empty() && sum < n){
		prim_node now = q.top();
		q.pop();
		if(vis[now.u]) continue;
		vis[now.u] = 1;
		sum++;
		ans += now.dis;
		for(int i = head[now.u]; i; i = e[i].next){
			if(e[i].w < dis[e[i].to]){
				dis[e[i].to] = e[i].w;
				q.push({e[i].to, dis[e[i].to]});
			}
		}
	}
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	memset(dis, 25, sizeof(dis));
	prim();
	if(sum == n){
		cout << ans << endl;
		return 0;
	}
	cout << "orz" << endl;
	return 0;
}
2023/7/31 15:49
加载中...