记录编号 |
315603 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[NOIP 2014]寻找道路 |
最终得分 |
100 |
用户昵称 |
NewBee |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.082 s |
提交时间 |
2016-10-05 16:57:00 |
内存使用 |
32.84 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Begin freopen("roadb.in","r",stdin);freopen("roadb.out","w",stdout);chul();Cu;
using namespace std;
const int maxn=10010*10;
struct op{
int to,next;
}r[maxn*20],rer[maxn*20];
int head[maxn],rehead[maxn],clr[maxn],tim,cnt,dis[maxn];
bool flag[maxn];
class po{
public:
int front(){
return q[F(head)];
}
bool empty(){
return head>tail;
}
void push(int x){
if(empty()){
push_front(x);
return;
}
if(dis[x]>=dis[front()]){
push_back(x);
}
else push_front(x);
}
void pop(){
head++;
}
private:
int head,tail;
int q[maxn];
int F(int x){
return (((x%maxn)+maxn)%maxn);
}
void push_front(int x){
q[F(--head)]=x;
}
void push_back(int x){
q[F(++tail)]=x;
}
}q;
void insert(int fr,int to){
tim++;
r[tim].to=to;
r[tim].next=head[fr];
head[fr]=tim;
}
void reinsert(int fr,int to){
cnt++;
rer[cnt].to=to;
rer[cnt].next=rehead[fr];
rehead[fr]=cnt;
}
void find(int rt){
clr[rt]=3;
int y;
for(int i=rehead[rt];i;i=rer[i].next){
y=rer[i].to;
if(!clr[y])find(y);
}
}
void refind(int rt){
clr[rt]=2;
int y;
for(int i=rehead[rt];i;i=rer[i].next){
y=rer[i].to;
if(clr[y]==3){
clr[y]=2;
continue;
}
else if(clr[y]!=2)refind(y);
}
}
void spfa(int fr,int to){
q.push(fr);
while(!q.empty()){
int x=q.front();q.pop();
flag[x]=0;
int y=0;
for(int i=head[x];i;i=r[i].next){
y=r[i].to;
if(clr[y]==2)continue;
if(dis[y]>dis[x]+1){
dis[y]=dis[x]+1;
if(!flag[y]){
q.push(y);
flag[y]=1;
}
}
}
}
}
void chul(){
int n,m;
int s,t;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&s,&t);
insert(s,t);
reinsert(t,s);
}
scanf("%d%d",&s,&t);
find(t);
for(int i=1;i<=n;i++){
if(!clr[i])refind(i);
}
if(clr[s]==2){
printf("-1\n");
return;
}
memset(dis,0x7f,sizeof(dis));
dis[s]=0;
spfa(s,t);
printf("%d\n",dis[t]);
}
int main(){
Begin;
}