关于prim的问题
查看原帖
关于prim的问题
1112330
hczyy楼主2025/8/1 14:49
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, M = 1e4 + 10;
#define LL long long
struct Node{
	int y, l;
};

struct Node2{
	int pos, dis;
	bool operator<(const Node2 a)const{
		return dis > a.dis;	
	}
};

int n, m, k, dis[N], cnt;
LL ans;
vector<Node>edge[N];
priority_queue<Node2>q;
bool vis[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> k;
	for(int i = 1; i <= m; i++){
		int x, y, l;
		cin >> x >> y >> l;
		edge[x].push_back({y, l});
		edge[y].push_back({x, l});
	}
	for(int i = 0; i <= n; i++){
		dis[i] = INT_MAX;
	}
	dis[1] = 0;
	q.push({1, 0});
	while(q.size()){
		int x = q.top().pos, val = q.top().dis;
		q.pop();
		if(vis[x]) continue;
		vis[x] = true;
		cnt++;
		ans += dis[x];
		if(cnt == n - k + 1) break;
		for(int i = 0; i < edge[x].size(); i++){
			int y = edge[x][i].y, l = edge[x][i].l;
			if(dis[y] > l){
				dis[y] = l;
				q.push({y, l});
			}
		}
	}
	if(cnt != n - k + 1) cout << "No Answer";
	else cout << ans;
	return 0; 
}

这是代码 我的问题是为什么43行 ans不能加val 只能加dis[x] 不然wa on 7 但是理论上只有dis[x]更新就会进堆然先于其他重复节点但是val更大的遍历 为什么不过呢 数据下下来也确实错了 求问

2025/8/1 14:49
加载中...