社区讨论

迪杰斯特拉的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 条回复,欢迎继续交流。

正在加载回复...