比赛 EYOI常规赛 9th 评测结果 AAAAAAAAAA
题目名称 寻找道路 最终得分 100
用户昵称 MAXFWL 运行时间 0.167 s
代码语言 C++ 内存使用 2.69 MiB
提交时间 2023-03-17 20:42:03
显示代码纯文本
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;

const int MAXN = 1e4 + 10;
const int MAXM = 2e5 + 10;
int n, m, s, t, tot=0, ava[MAXN], ava2[MAXN], vis[MAXN];
int head[MAXN*2], v[MAXM*2], nxt[MAXM*2];
struct node{
	int u, step;
}; queue<node> q;

void add(int a, int b){
	v[++tot] = b;
	nxt[tot] = head[a];
	head[a] = tot;
}

void bfs1(){
	queue<int> qq; qq.push(t+n); ava[t]=true;
	while (!qq.empty()){
		int u = qq.front(); qq.pop();
		for (int i = head[u]; i; i = nxt[i]){
			int ver = v[i];
			if (!ava[ver-n])
				{ava[ver-n] = true; qq.push(ver);}
		}
	}
}

int bfs(){
	q.push({s, 0}); vis[s] = 1;
	while (!q.empty()){
		int u = q.front().u;
		int step = q.front().step; q.pop();
		if (u == t)	return step;
		for (int i = head[u]; i; i = nxt[i]){
			int ver = v[i];
			if (ava2[ver] && !vis[ver])
				{vis[ver] = 1; q.push({ver, step+1});}
		}
	} return -1;
}

int main(){
	freopen("roadb.in", "r", stdin);
	freopen("roadb.out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int x, y; cin >> x >> y;
		add(x, y); add(y+n, x+n);
	} cin >> s >> t;
	
	bfs1(); for (int i = 1; i <= n; i++){
		if (!ava[i])  ava2[i] = false;
		else ava2[i] = true;
		for (int j = head[i]; j; j = nxt[j])
			ava2[i] = ava2[i] & ava[v[j]];
	}
	
	int ans = bfs();
	cout << ans << endl;
	
	return 0;
}