【洛谷P2296】[NOIP2014]寻找道路

寻找道路

题目链接

这道题非常的水，按照题意，

先反向建边，从终点搜索，标记出可以到达终点的点

然后枚举一遍，判断出符合条件1的点

再从起点搜索一遍就可以了

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 #define N 10010

 #define M 200010

 int n,m,Head[N],_Head[N],dis[N],tot,s,t;

 int que[M],head,tail;

 bool vis[N],ok[N];

 inline int read(){

     int x=; char c=getchar();

     while(c<''||c>'') c=getchar();

     while(''<=c&&c<='') { x=(x<<)+(x<<)+c-''; c=getchar(); }

     return x;

 }

 struct NODE{

     int to,next;

 } e[M],_e[M];

 inline void add(int x,int y){

     e[++tot].to=y;

     e[tot].next=Head[x];

     Head[x]=tot;

     _e[tot].to=x;

     _e[tot].next=_Head[y];

     _Head[y]=tot;

 }

 int main()

 {

     n=read(); m=read();

     int x,y;

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

         x=read(); y=read();

         add(x,y);

     }

     s=read(); t=read();

     que[++tail]=t; vis[t]=;

     while(head<tail){

         int u=que[++head];

         for(int i=_Head[u];i;i=_e[i].next){

             int v=_e[i].to;

             if(!vis[v]){

                 vis[v]=;

                 que[++tail]=v;

             }

         }

     }

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

         bool flag=;

         for(int j=Head[i];j;j=e[j].next)

          if(!vis[e[j].to]) {

              flag=; break;

          }

         ok[i]=flag;

     }

     head=tail=;

     que[++tail]=s;

     dis[s]=;

     while(head<tail){

         int u=que[++head];

         if(u==t) break;

         for(int i=Head[u];i;i=e[i].next){

             int v=e[i].to;

             if(!dis[v]&&ok[v]){

                 dis[v]=dis[u]+;

                 que[++tail]=v;

             }

         }

     }

     if(dis[t])

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

     else

         puts("-1");

     return ;

 }