我的Dijkstra还有什么可以改进的地方吗?
  • 板块学术版
  • 楼主ass_wecan
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/7/21 17:19
  • 上次更新2023/10/27 19:04:03
查看原帖
我的Dijkstra还有什么可以改进的地方吗?
505805
ass_wecan楼主2022/7/21 17:19

正确性保证,想要降低常数,剪剪枝,求指导!

inline void Dijkstra(int s){
	for(register int i=1;i<=n*(use+1);++i)
		dis[i]=INF;dis[s]=0;
	priority_queue<node> q;
	q.push((node){0,s});
	while(!q.empty()){
		int u=q.top().now;
		q.pop();
		if(vis[u])	continue;
		vis[u]=1;
		for(register int i=head[u];i;i=Edge[i].nxt){
			int v=Edge[i].to,w=Edge[i].dis;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push((node){dis[v],v});
			}
		}
	} 
}
2022/7/21 17:19
加载中...