求调堆优化prim
查看原帖
求调堆优化prim
781046
tai_chi楼主2023/3/30 23:36

RT,调了半天了,救救孩子吧qwq

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, m;
struct node
{
	int v, w;
	friend bool operator<(node x, node y)
	{
		return x.w < y.w;
	}
};
vector<node> gr[maxn];
priority_queue<node> q;
int dis[maxn];
bool vis[maxn];
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		gr[u].push_back(node{v, w});
		gr[v].push_back(node{u, w});
	}
	int ans = 0, tot = 0;
	memset(dis, 0x3f, sizeof(dis));
	dis[1] = 0;
	q.push(node{1, 0});
	while (!q.empty() && tot < n)
	{
		node now = q.top();
		q.pop();
		int u = now.v, d = now.w;
		if (vis[u])
			continue;
		vis[u] = 1;
		ans += d;
		tot++;
		for (node to : gr[u])
		{
			int v = to.v, w = to.w;
			if (!vis[v] && dis[v] > w)
			{
				dis[v] = w;
				q.push(node{v, dis[v]});
			}
		}
	}
	if (tot == n)
		cout << ans << endl;
	else
		cout << "orz" << endl;
	return 0;
}
2023/3/30 23:36
加载中...