关于dij
  • 板块学术版
  • 楼主Tzs_yousa
  • 当前回复11
  • 已保存回复11
  • 发布时间2022/6/1 20:56
  • 上次更新2023/10/28 00:07:50
查看原帖
关于dij
453100
Tzs_yousa楼主2022/6/1 20:56
while(!q.empty()){
		int u=q.top().id;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=hd[u];i;i=e[i].nxt){
			int to=e[i].v;
			if(dis[to]>dis[u]+e[i].w){
				dis[to]=dis[u]+e[i].w;
				q.push(node{dis[to],to});
			}
		} 
	}

对于这样一份优先队列优化的dij,vis数组在有向无环图是不是可以舍去,只存在正环可以舍去吗,可以判断负环吗

2022/6/1 20:56
加载中...