社区讨论
迪杰斯特拉的vis数组是不是不必要的呢
学术版参与者 7已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @mhj00vpf
- 此快照首次捕获于
- 2025/11/03 18:30 4 个月前
- 此快照最后确认于
- 2025/11/03 18:30 4 个月前
CPP
void dij(int s,int k){
priority_queue<pair<double,pii> > q;
while(q.size())q.pop();
q.push({0,{s,0}});
dis[s][0]=0;
while(q.size()){
int u=q.top().se.fi,ci=q.top().se.se;
q.pop();
// if(vis[u][ci])
// continue;
// vis[u][ci]=1;
for(auto x:g[u]){
int v=x.fi,w=x.se;
if(v==s)
continue;
int cc=ci+sp[v];
cc=min(cc,k);
if(dis[v][cc]>dis[u][ci]+cl(w,ci)){
dis[v][cc]=dis[u][ci]+cl(w,ci);
q.push({-dis[v][cc],{v,cc}});
}
}
}
}
感觉应该可以去掉,如果直接用dis数组更新的话。或者我想错了吗
回复
共 7 条回复,欢迎继续交流。
正在加载回复...