社区讨论
Dijkstra队列为什么不能只放一个整数?
P3371【模板】单源最短路径(弱化版)参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mlh9k4nz
- 此快照首次捕获于
- 2026/02/11 08:00 上周
- 此快照最后确认于
- 2026/02/12 17:20 上周
我的想法是如下定义
CPPstruct 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 条回复,欢迎继续交流。
正在加载回复...