寻找道路（NOIP2014）神奇之题。。

原题传送门

这道题嘛。。

首先根据题目，我们要先知道哪些点能够到达终点。（反向BFS）

然后我们再求最短路的途中，必须随时判断周围的点是否被第一次BFS标记过。、

所以再来一次BFS。

数组记得清零，不然会炸。。

下面贴代码

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,m,num=,s,tt;

int q[];

int step[];

int head[];

bool vis[];

int a[],b[];

struct edge{

    int to,next;

}g[];

void ins(int u,int v)

{

    g[++num].next=head[u];

    head[u]=num;

    g[num].to=v;

}

void bfs1(int last){

    vis[last]=true;

    int h=,t=;

    q[h]=last;

    while(h<=t)

    {

        int tmp=q[h];

        for(int i=head[tmp];i;i=g[i].next)

        if(!vis[g[i].to])

        {

            vis[g[i].to]=true;

            q[++t]=g[i].to;

        }

        h++;

    }

}

bool chubian(int q){

    for(int i=head[q];i;i=g[i].next)

    if(!vis[g[i].to]) return false;

    return true;

}

bool bfs2(int first){

    memset(q,,sizeof(q));

    int h=,t=;

    q[h]=first;

    while(h<=t)

    {

        int tmp=q[h++];

        if(!chubian(tmp))continue;

        for(int i=head[tmp];i;i=g[i].next)

        if(step[g[i].to]==)

        {

            step[g[i].to]=step[tmp]+;

            if(g[i].to==tt){printf("%d\n",step[tt]);return true;}

            q[++t]=g[i].to;

        }

    }

    return false;

}

int main(){

    scanf("%d%d",&n,&m);

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

    {

        scanf("%d%d",&a[i],&b[i]);

        ins(b[i],a[i]);

    }

    scanf("%d%d",&s,&tt);

    bfs1(tt);

    memset(head,,sizeof(head));

    memset(g,,sizeof(g));

    num=;

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

    ins(a[i],b[i]);

    if(!bfs2(s))printf("-1\n");

}