prim优先队列86分求助
查看原帖
prim优先队列86分求助
1290335
why2004楼主2024/3/13 14:41
#include <iostream>
#include <queue>;
#include<vector>;
#include <climits>
using namespace std;

vector<pair<int, int> >mp[5010];

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;

int n, m, k = 0, vis[5010];
long long sum;
vector<int> ans(5010, 10001);

int main()
{

	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b, d;
		cin >> a >> b >> d;
		mp[a].push_back(make_pair(d, b));
		mp[b].push_back(make_pair(d, a));
	}
	//直接从点1开始遍历
	vis[1] = 1;
	ans[1] = 0;
	for (auto it : mp[1]) {
		ans[it.second] = it.first;
		q.push(it);
	}
	while (!q.empty()) {
		int x, y;
		pair<int, int> temp;
		temp = q.top();
		q.pop();
		x = temp.second;
		y = temp.first;
		if (vis[x] == 1) continue;
		vis[x] = 1;
		for (auto it : mp[x]) {
			if (vis[it.second] != 1 && ans[it.second] > it.first) {
				ans[it.second] = it.first;
				q.push(make_pair(it.first, it.second));
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		sum += ans[i];
	}
	for (int i = 1; i <= n; i++) {
		k = k + vis[i];
	}
	if (k == n) {
		cout << sum;
	}
	else {
		cout << "orz";
	}
	return 0;
}
2024/3/13 14:41
加载中...