社区讨论

关于prim的问题

P1195口袋的天空参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mdsgsoro
此快照首次捕获于
2025/08/01 14:50
7 个月前
此快照最后确认于
2025/11/04 03:22
4 个月前
查看原帖
CPP
#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更大的遍历 为什么不过呢 数据下下来也确实错了 求问

回复

2 条回复,欢迎继续交流。

正在加载回复...