题目

90分提交记录

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, e[200100][2], hd[200100][2], ne[200100][2], idx, a, b, s, t, dis[10000];
bool vis[200100], f[200100];
void add(int a, int b){//双向存图
	e[idx][0] = b;
	ne[idx][0] = hd[a][0];
	hd[a][0] = idx;
	e[idx][1] = a;
	ne[idx][1] = hd[b][1];
	hd[b][1] = idx;
	idx++;
}
void bfs(bool o){
	memset(vis, 0, sizeof vis);
	queue<int> q;
	if(o){//反向
		q.push(t);
		vis[t] = 1;
		while(!q.empty()){
			int x = q.front();
			q.pop();
			for(int i = hd[x][o];i !=-1;i = ne[i][o]){
				if(!vis[e[i][o]]){
					f[e[i][o]] = 1;//可以走
					q.push(e[i][o]);
					vis[e[i][o]] = 1;
				}
			}
		}
	}
	else{//正向
		q.push(s);
		vis[s] = 1;
		while(!q.empty()){
			int x = q.front();
			q.pop();
			bool p = false;
			for(int i = hd[x][o]; i != -1;i = ne[i][o]){
				if(!f[e[i][o]]){
					p=true;
					break;
				}
			}
			if(p){
				continue;//不能走
			}
			for(int i = hd[x][o]; i != -1;i = ne[i][o]){
				if(!vis[e[i][o]]){
					dis[e[i][o]] = dis[x] + 1;
					vis[e[i][o]] = 1;
					q.push(e[i][o]);
				}
			}
		}
	}
}
int re;
char c;
int read(){
	re=0;
	c=getchar();
	while(c<'0'||c>'9'){
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		re=(re<<3)+(re<<1)+(c^48);
		c=getchar();
	}
	return re;
}
void write(int x){
	if(x/10){
		write(x/10);
	}
	putchar(x%10|48);
}
signed main(){
	memset(hd, -1, sizeof hd);
	n=read();m=read();
	for(int i = 1;i <= m;i++){
		a=read();b=read();
		add(a,b);
	}
	s=read();
	t=read();
	bfs(1);
	f[t] = 1;
	bfs(0);
	if(!dis[t]){
		printf("-1\n");
	}
	else{
		printf("%d", dis[t]);
	}
	return 0;
}