社区讨论

Dijkstra判负环

P5960【模板】差分约束参与者 2已保存回复 1

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@mjcn3mxl
此快照首次捕获于
2025/12/19 17:01
2 个月前
此快照最后确认于
2025/12/21 09:50
2 个月前
查看原帖
CPP
bool dijk(){
	priority_queue<pt>q;
	q.push({0,0});
	while(q.size()){
		pt now=q.top();q.pop();
		if(now.dis<sum)return 0;
		if(now.dis>dis[now.t])continue;
		int len=ve[now.t].size();
		for(int i=0;i<len;i++){
			int aw=ve[now.t][i].v;
			if(dis[aw]>now.dis+ve[now.t][i].w){
				dis[aw]=now.dis+ve[now.t][i].w;
				q.push({aw,dis[aw]});
			}
		}
	}return 1;
}
//
	for(int i=1;i<=m;i++){
		int b,e,t;
		cin>>b>>e>>t;
		ve[e].push_back({b,t});
		if(t<=0)sum+=t;
	}
不知道原理

回复

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

正在加载回复...