BFS队列优化

$inq[u]$表示$u$是否在队列中(important)

该方法也使用与SPFA上

void bfs()
{
    int l=0,r=1;
    memset(dis,1,sizeof(dis));
    q[1].x=1,dis[1]=0,inq[1]=1;
    while (l<r)
    {
        ++l;
        node now=q[l];
        inq[now.x]=0;
        //出队之后,inq[u]=0;
        for (int i=first[now.x];i!=-1;i=nxt[i])
        {
            int u=point[i],dd=dis[now.x]+val[i];
            //注意此处不用now.d,要用结构体外的dis数组！！！！！！ 
            checkmin(dis[u],dd);
            //更新最小值
            if (inq[u])
            {
                continue;
                //已入队的点直接更新即可，不用再入队。
            }
            else
            {
                ++r;
                q[r].x=u;
                inq[u]=1;
            }
        }
    }
    for (int i=1;i<=n;++i)
    {
        printf("%d\n",dis[i]);
    }
}

BFS队列优化

原文：https://www.cnblogs.com/mayiyang/p/11312884.html