社区讨论
想请问大佬,为什么用优先队列会T一个数据,而普通队列则不会呢
P3385【模板】负环参与者 6已保存回复 11
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 11 条
- 当前快照
- 1 份
- 快照标识符
- @loca8sp8
- 此快照首次捕获于
- 2023/10/30 10:30 2 年前
- 此快照最后确认于
- 2023/11/04 22:18 2 年前
优先队列版本
CPPvoid spfa() {
priority_queue<pii, vector<pii>, greater<pii> > heap;
heap.push({0, 1}); vis[1] = 1;
while(heap.size()) {
ll t = heap.top().second; heap.pop(); vis[t] = 0;
for(int i = h[t]; i != -1; i = edges[i].next) {
int j = edges[i].e;
if(dist[j] > dist[t] + edges[i].w) {
dist[j] = dist[t] + edges[i].w;
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n) {
cout << "YES\n";
return ;
}
if(vis[j] == 0) {
vis[j] = 1;
heap.push({dist[j], j});
}
}
}
}
cout << "NO\n";
return ;
}
回复
共 11 条回复,欢迎继续交流。
正在加载回复...