Prim堆优化求调(最后一个 AC,其它 WA)
查看原帖
Prim堆优化求调(最后一个 AC,其它 WA)
804607
rainygame楼主2023/6/7 15:21

代码应该符合 Python 代码规范。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 5001

int n, m, u, v, w, ans;
int dis[MAXN];
bitset<MAXN> vis;

struct Node{
	int u, dis;
	bool operator>(const Node b)const{
		return dis > b.dis;
	}
}node;
priority_queue<Node, vector<Node>, greater<Node>> pq;

struct Edge{
	int v, w;
};
vector<Edge> e[MAXN];

int prim(){
	dis[1] = 0;
	pq.push({1, 0});
	
	int ans(0), cnt(0);
	while (!pq.empty() && cnt < n){
		node = pq.top();
		pq.pop();
		if (vis.test(node.u)) continue;
		vis.set(node.u);
		
		++cnt;
		ans += node.dis;
		for (auto i: e[node.u]){
			if (i.w < dis[i.v]){
				dis[i.v] = i.w;
				pq.push({i.v, dis[i.v]});
			}
		}
	}
	
	return (cnt == n ? ans : -1);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m;
	while (m--){
		cin >> u >> v >> w;
		e[u].push_back({v, w});
	}
	
	memset(dis, 0x3f, sizeof(dis));
	ans = prim();
	if (ans == -1) cout << "orz";
	else cout << ans;
	
	return 0;
}

2023/6/7 15:21
加载中...