记录编号	174550	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]寻找道路	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	0.158 s
提交时间	2015-08-01 19:53:24	内存使用	3.73 MiB

#include<cstdio>

using namespace std;

int n,m,s,t;
int arrive[200010],dis[200010];
int first[10010],tot,reach[200010];


struct Edge{
    int zd,next;
}edge[200010];

void add(int qd,int zd)
{
    edge[++tot].zd=zd;
    edge[tot].next=first[qd];
    first[qd]=tot;
}

void bfs()
{
    int q[200010]={0};
    bool v[200010]={0};
    int head=0,tail=-1;
    q[++tail]=t;v[t]=1;
    arrive[t]=1;
    while(head<=tail)
    {
        int p=q[head];head++;
        for(int i=first[p];i;i=edge[i].next)
            if(!v[edge[i].zd])
            {
                q[++tail]=edge[i].zd;
                v[edge[i].zd]=1;
                arrive[edge[i].zd]=1;
            }
    }
    for(int i=1;i<=n;i++)
        if(!arrive[i])
        {
            reach[i]=1;
            for(int k=first[i];k;k=edge[k].next)
                reach[edge[k].zd]=1;
        }
}

void spfa()
{
    bool v[200010]={0};
    int q[200010]={0};
    int head=0,tail=-1;
    for(int i=1;i<=n;i++)
        dis[i]=1000000;
    dis[t]=0;
    q[++tail]=t;v[t]=1;
    while(head<=tail)
    {
        int p=q[head];
        head++;v[p]=0;
        for(int i=first[p];i;i=edge[i].next)      
        {
            int zd=edge[i].zd;
            if(!reach[zd])
            {
                if(dis[zd]>dis[p]+1)
                {
                    dis[zd]=dis[p]+1;
                    if(!v[zd])
                    {
                        v[zd]=1;
                        q[++tail]=zd;
                    }
                }
            }
        }    
    }
    printf("%d",dis[s]);
}

int main()
{
    freopen("roadb.in","r",stdin);
	freopen("roadb.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1,qd,zd;i<=m;i++)
    {
        scanf("%d%d",&qd,&zd);
        if(zd!=qd)
            add(zd,qd);
    }
    scanf("%d%d",&s,&t);
    bfs();
    spfa();
}
/*
6 6
1 3
1 2
2 6
2 5
4 5
3 4
1 5
*/