dijkstra 为啥不能这样写
查看原帖
dijkstra 为啥不能这样写
749630
wxzzzz楼主2024/4/27 09:07

AC:

while(!q.empty())
{
	int x=q.top().second;
	q.pop();
	if(flag[x]) continue;
	flag[x]=1;
	for(int i=h[x];~i;i=ne[i])
	{
		int y=v[i];
		if(dis[x]+e[i]<dis[y])
		{
			dis[y]=dis[x]+e[i];
			q.push({dis[y],y});
		}
	}
}

WA:

flag[st]=1;
while(!q.empty())
{
	int x=q.top().second;
	q.pop();
	if(flag[x]) continue;
	flag[x]=1;
	for(int i=h[x];~i;i=ne[i])
	{
		int y=v[i];
		if(dis[x]+e[i]<dis[y])
		{
			dis[y]=dis[x]+e[i];
        if(!flag[y])
			{
				flag[y]=1;
				q.push({dis[y],y});
			}
		}
	}
}
2024/4/27 09:07
加载中...