Luogu P3645 [APIO2015]雅加达的摩天楼

2021-05-17 14:28

阅读：494

标签：pac return its turn can ack tuple ref scan

题目
直接BFS求01最短路。
因为状态是\(O(n\sqrt n)\)级别的所以没有问题。
注意判断某个hl是否经过某个点要用bitset。

#include
#define pb push_back
using namespace std;
const int N=30007;
vectordog[N];
bitsetvis[N];
queue>q;
int used[N],n,m,s,t;
int read(){int x;scanf("%d",&x);return x;}
void move(int p,int id,int step)
{
    if(!used[p])
    {
        used[p]=1;
        for(int x:dog[p]) if (!vis[p][x]) vis[p][x]=1,q.emplace(p,x,step);
    }
    if(~id&&!vis[p][id]) vis[p][id]=1,q.emplace(p,id,step);
}
int main()
{
    n=read(),m=read();int i,b,p,step;
    for(i=0;i^m;++i)
    {
    b=read(),p=read();
    if(!i) s=b;
    if(i==1) t=b;
    dog[b].pb(p);
    }
    if(s==t) return !printf("0");
    move(s,-1,0);
    while(!q.empty())
    {
        tie(b,p,step)=q.front(),q.pop();
        if(b==t) return !printf("%d",step);
        if(b-p>=0) move(b-p,p,step+1);
        if(b+p

Luogu P3645 [APIO2015]雅加达的摩天楼

标签：pac return its turn can ack tuple ref scan

原文地址：https://www.cnblogs.com/cjoierShiina-Mashiro/p/11774267.html

上一篇：win10系统ping另一台电脑上虚拟机的IP

下一篇：C#调试

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Luogu P3645 [APIO2015]雅加达的摩天楼
文章链接：http://soscw.com/index.php/essay/86748.html

亲，登录后才可以留言！

Luogu P3645 [APIO2015]雅加达的摩天楼

评论

热门文章

推荐文章

最新文章

置顶文章