洛谷P2296 寻找道路

Code:
#include<cstdio>

#include<queue>

#include<algorithm>

using namespace std;

const int maxn = 200000 + 3;

int head[maxn<<1], to[maxn<<1], nex[maxn<<1], cnt;

int mark[maxn], du[maxn], vis[maxn],d[maxn],del[maxn];

queue<int>Q;

inline void add_edge(int u,int v)

{

    nex[++cnt] = head[u], head[u] = cnt, to[cnt] = v;

}

inline void solve(int s)

{

    Q.push(s);

    mark[s] = 1;

    while(!Q.empty())

    {

        int u = Q.front();Q.pop();

        for(int v = head[u]; v ; v = nex[v])

            if(!mark[to[v]])

            {

                mark[to[v]] = 1;

                Q.push(to[v]);

            }

    }

}

int main()

{

    //freopen("in.txt","r",stdin);

    int n,m;

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

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

    {

        int a,b;

        scanf("%d%d",&a,&b);

        add_edge(b,a);

        du[a] = 1;

    }

    int s,t;

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

    solve(t);

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

    {

        if(!mark[i])

        {

            del[i] = 1;

            for(int v = head[i]; v ; v = nex[v])

            {

                del[to[v]] = 1;

            }

        }

    }

    Q.push(t);

    vis[t] = 1, d[s] = -1;

    while(!Q.empty())

    {

        int u = Q.front();Q.pop();

        for(int v = head[u]; v ; v = nex[v])

            if(!vis[to[v]] && !del[to[v]])

            {

                vis[to[v]] = 1, d[to[v]] = d[u] + 1;

                Q.push(to[v]);

            }

        if(vis[s]) break;

    }

    printf("%d",d[s]);

    return 0;

}
巴特西

洛谷P2296 寻找道路_简单BFS

最新文章

热门文章
