题面见COGS
啊啊啊啊啊啊啊啊啊,被这大水题卡了一天(这是要填昨天的坑的博文),我果然还是太弱啊。
这么水的题,只用正反两遍BFS就好了,直接贴代码,
一如既往地没有注释。
#include
#include
#include
#include
#include
using namespace std;
const int MXM = 200005;
const int MXN = 10005;
int head[MXN], head2[MXN], tot, s, t, m, n;
int dis[MXN];
bool ok[MXN], can[MXN];
struct edge{
int fr, to, ne;
}e[MXM], e2[MXM];
void addedge(int a, int b) {
tot++;
e[tot].fr = a;
e2[tot].fr = b;
e[tot].to = b;
e2[tot].to = a;
e[tot].ne = head[a];
head[a] = tot;
e2[tot].ne = head2[b];
head2[b] = tot;
}
bool vis[MXN];
void bfs1() {
queue q;
q.push(t);
can[t] = true;
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = head2[now]; i; i = e2[i].ne) {
int to = e2[i].to;
if (!vis[to]) {
can[to] = true;
vis[to] = true;
q.push(to);
}
}
}
memset(vis, 0, sizeof(vis));
}
void bfs2() {
queue q;
q.push(s);
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = head[now]; i; i = e[i].ne) {
int to = e[i].to;
if (!vis[to]) {
if (ok[to]) {
dis[to] = dis[now] + 1;
q.push(to);
}
vis[to] = true;
}
}
}
}
int main() {
//freopen("roadb.in", "r", stdin);
//freopen("roadb.out", "w", stdout);
scanf("%d%d", &n, &m);
int x, y;
for (int i = 1; i <= m; i++) {
scanf("%d%d", &x, &y);
addedge(x, y);
}
scanf("%d%d", &s, &t);
bfs1();
memset(ok, 1, sizeof(ok));
queue q;
q.push(s);
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = head[now]; i; i = e[i].ne) {
int to = e[i].to;
if (!can[e[i].to]) {
ok[e[i].fr] = false;
}
if (!vis[to]) {
vis[to] = true;
q.push(to);
}
}
}
if (!ok[s]) {
printf("-1\n");
return 0;
}
memset(vis, 0, sizeof(vis));
bfs2();
if (!dis[t]) {
printf("-1\n");
return 0;
}
printf("%d\n", dis[t]);
return 0;
}