记录编号 |
442518 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[NOIP 2014]寻找道路 |
最终得分 |
100 |
用户昵称 |
CSU_Turkey |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.131 s |
提交时间 |
2017-08-27 17:30:02 |
内存使用 |
3.56 MiB |
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int n,m,s,t,head1[10005],h1,head2[10005],h2,vis[10005],book[10005],dis[10005];
struct edge{
int to,next;
}e1[200005],e2[200005];
void edge_add(int x,int y){
e1[++h1].to=y;
e1[h1].next=head1[x];
head1[x]=h1;
e2[++h2].to=x;
e2[h2].next=head2[y];
head2[y]=h2;
}
void bfs(){
queue<int>S;
S.push(t);
vis[t]=1;
while(!S.empty()){
int u=S.front();
S.pop();
for(int i=head2[u];i;i=e2[i].next){
if(!vis[e2[i].to]){
vis[e2[i].to]=1;
S.push(e2[i].to);
}
}
}
}
void spfa(){
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
book[s]=1;
queue<int>S;
S.push(s);
while(!S.empty()){
int u=S.front();
S.pop();
book[u]=0;
for(int i=head1[u];i;i=e1[i].next){
int v=e1[i].to,bo=0;
for(int j=head1[v];j;j=e1[j].next){
if(!vis[e1[j].to]){
bo=1;
break;
}
}
if(bo)continue;
if(dis[v]>dis[u]+1){
dis[v]=dis[u]+1;
if(!book[v]){
S.push(v);
book[v]=1;
}
}
}
}
if(dis[t]==dis[0])
cout<<-1;
else
cout<<dis[t];
}
int main()
{
freopen("roadb.in","r",stdin);
freopen("roadb.out","w",stdout);
// freopen("1.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
edge_add(x,y);
}
scanf("%d%d",&s,&t);
bfs();
spfa();
return 0;
}