洛谷 P2296 寻找道路 —— bfs

题目：https://www.luogu.org/problemnew/show/P2296

第一次用 Emacs 对拍，写了半天；

注意那个 is 赋值的地方很容易错，千万别反复赋值；

一道水题写了一个下午，崩溃。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int const maxn=1e4+,maxm=2e5+;

int n,m,s,t,hd[maxn],ct,to[maxm],nxt[maxm],dis[maxn],hdf[maxn],tof[maxm],nxtf[maxm],ctf;

bool vis[maxn],is[maxn];

queue<int>q;

void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}

void add2(int x,int y){tof[++ctf]=y; nxtf[ctf]=hdf[x]; hdf[x]=ctf;}

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}

  while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return ret*f;

}

void init()

{

  q.push(t); vis[t]=; is[t]=;

  while(q.size())

    {

      int x=q.front(); q.pop();

      for(int i=hdf[x],u;i;i=nxtf[i])

    {

      if(vis[u=tof[i]])continue;

      vis[u]=; q.push(u); is[u]=;//is=1

    }

    }

  for(int i=;i<=n;i++)

    {

      //      if(vis[i]){is[i]=1; continue;}

      if(vis[i])continue;

      for(int j=hdf[i];j;j=nxtf[j])

    is[tof[j]]=;

    }

}

void bfs()

{

  memset(vis,,sizeof vis);

  while(q.size())q.pop();

  q.push(s); vis[s]=;

  while(q.size())

    {

      int x=q.front(); q.pop();

      for(int i=hd[x],u;i;i=nxt[i])

    {

      if(vis[u=to[i]]||!is[u])continue;

      vis[u]=; q.push(u); dis[u]=dis[x]+;

    }

    }

}

int main()

{

  n=rd(); m=rd();

  for(int i=,x,y;i<=m;i++)

    {

      x=rd(),y=rd();

      if(x==y)continue;

      add(x,y),add2(y,x);

    }

  s=rd(); t=rd();

  init();

  if(!is[s]){printf("-1\n"); return ;}//

  bfs();

  if(!vis[t])printf("-1\n");

  else printf("%d\n",dis[t]);

  return ;

}