记录编号 315603 评测结果 AAAAAAAAAA
题目名称 [NOIP 2014]寻找道路 最终得分 100
用户昵称 GravatarNewBee 是否通过 通过
代码语言 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;
}