比赛 |
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;
}