通过%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那样也可以求无权最短路,哪里出了问题了呢,大佬教教

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

相关推荐

totoroyyw:千年老妖😂
投递华为等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务