通过%92 ,想不明白。

int  bfs()
{
    memset(cnt,0x3f,sizeof cnt);
    cnt[1]=0;
    q.push({0,1});
    while(q.size())
    {
        auto t=q.front();q.pop();
        int ver=t.second;
        if(st[ver])continue;
        st[ver]=true;
        for(int i=h[ver];~i;i=ne[i])
        {
            int j=e[i];
            if(!st[j]&&cnt[ver]+1<cnt[j])//cnt[ver]+1<cnt[j]
            {
                cnt[j]=cnt[ver]+1;
                q.push({cnt[j],j});
            }

        }
    }
    return cnt[n];
}

I题:https://ac.nowcoder.com/acm/contest/46814/I 为什么那个bfs()把注释那里的cnt[ver]+1<cnt[j]cnt[ver]+1<cnt[j] 删掉就过不了(上面的是正确的),印象中bfs不用像dijikstra那样也可以求无权最短路,哪里出了问题了呢,大佬教教

#牛客寒假算法基础集训营#
全部评论

相关推荐

鬼迹人途:你去投一投尚游游戏,服务器一面,第一个图算法,做完了给你一个策略题,你给出方案他就提出低概率问题,答不上当场给你挂
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务