社区讨论
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 条回复,欢迎继续交流。
正在加载回复...