社区讨论

想请问大佬,为什么用优先队列会T一个数据,而普通队列则不会呢

P3385【模板】负环参与者 6已保存回复 11

讨论操作

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

当前回复
11 条
当前快照
1 份
快照标识符
@loca8sp8
此快照首次捕获于
2023/10/30 10:30
2 年前
此快照最后确认于
2023/11/04 22:18
2 年前
查看原帖
优先队列版本
CPP
void 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 条回复,欢迎继续交流。

正在加载回复...