【洛谷P2296】寻找道路

反正图两边bfs

 #include<iostream>

 #include<cstdio>

 #include<queue>

 using namespace std;

 inline int readint(){

     int x=,f=;

     char ch=getchar();

     while (ch<''||ch>''){

         if (ch=='-') f=-;

         ch=getchar();

     }

     while (ch>=''&&ch<=''){

         x=(x<<)+(x<<)+ch-'';

         ch=getchar();

     }

     return x*f;

 }

 struct edge{

     int x,nxt;

 }e1[],e2[];

 int n,m,s,t,t1,t2,kk,inq[],v[],tmp,sg=,v2[],v1[],cnt,head1[],head2[];

 struct node{

     int x,p;

 }now;

 inline void adde1(int a,int b){

     ++cnt;

     e1[cnt].x=b;

     e1[cnt].nxt=head1[a];

     head1[a]=cnt;

 }inline void adde2(int a,int b){

     ++cnt;

     e2[cnt].x=b;

     e2[cnt].nxt=head2[a];

     head2[a]=cnt;

 }

 queue <node> q;

 queue <int> qq;

 int main(){

     n=readint();

     m=readint();

     for (int i=;i<=m;++i){

         t1=readint();

         t2=readint();

         adde1(t1,t2);

         adde2(t2,t1);

     }

     s=readint();

     t=readint();

     kk=t;

     inq[kk]=;

     qq.push(kk);

     while (!qq.empty()){

         kk=qq.front();

         qq.pop();

         inq[kk]=;

         v1[kk]=;

         for (int i=head2[kk];i;i=e2[i].nxt){

             tmp=e2[i].x;

             if ((!inq[tmp])&&(!v1[tmp])) qq.push(tmp);

         }

     }

     for (int i=;i<=n;++i) v[i]=v1[i];

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

         if (v1[i]==) {

             v[i]=;

             for (int j=head2[i];j;j=e2[j].nxt){

                 v[e2[j].x]=;

             }

         }

     }

     q.push((node){s,});

     while (!q.empty()){

         now=q.front();

         q.pop();

         v2[now.x]=;

         if (now.x==t) printf("%d",now.p),sg=;

         if (sg==) break;

         for (int i=head1[now.x];i;i=e1[i].nxt){

             tmp=e1[i].x;

             if (v[tmp]==&&v2[tmp]==) {

                 q.push((node){tmp,now.p+});

             }

         }

     }

     if (sg==) printf("-1\n");

 }

STD