社区讨论

Dijkstra队列为什么不能只放一个整数?

P3371【模板】单源最短路径(弱化版)参与者 2已保存回复 3

讨论操作

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

当前回复
3 条
当前快照
1 份
快照标识符
@mlh9k4nz
此快照首次捕获于
2026/02/11 08:00
上周
此快照最后确认于
2026/02/12 17:20
上周
查看原帖
我的想法是如下定义
CPP
struct cmp {
	bool operator()(int a, int b) const{
		return dis[b] < dis[a];
	}
};
std::priority_queue<int, std::vector<int>, cmp>q;
一个很明显的问题是dis会不断变化,但我认为:对于一个被更新过的点u而言,它被入队时是根据变化过的dis[u]进行堆序调整的,此时虽然队内会出现两个一样的点,但是当后入的点被取出后,use[u]=true,旧点就没用了,故而不会影响堆的正确性
然而事实就是30pts,但我实在想不明白出现问题的逻辑,求解答T T(一定关注)
如果需要的话,我的完整代码如下:
CPP
#include<bits/stdc++.h>
const int N1 = 1e4 + 3;
const int N2 = 5e5 + 3;
int n, m, s, head[N1],cnt=0;
bool use[N1];
long long dis[N1];
struct edge {
	int to,next;
	long long val;
}edges[N2];
struct cmp {
	bool operator()(int a, int b) const{
		return dis[b] < dis[a];
	}
};
std::priority_queue<int, std::vector<int>, cmp>q;
int main() {
	scanf("%d %d %d", &n, &m, &s);
	std::fill(dis+1,dis+n+1,INT_MAX);
	int u, v, w;
	while (m--) {
		scanf("%d %d %d", &u, &v, &w);
		edges[++cnt].to = v;
		edges[cnt].next = head[u];
		edges[cnt].val = w;
		head[u] = cnt;
	}
	q.push(s);
	dis[s] = 0;
	while (!q.empty()) {
		int now = q.top();
		q.pop();
		if (use[now])continue;
		use[now] = true;
		for (int i = head[now]; i; i = edges[i].next) {
			int to = edges[i].to;
			if (dis[to] > dis[now] + edges[i].val) {
				dis[to] = dis[now] + edges[i].val;
				q.push(to);
			}
		}
	}
	for (int i = 1; i <= n; i++) printf("%lld ", dis[i]);
	return 0;
}

回复

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

正在加载回复...