题面见COGS
啊啊啊啊啊啊啊啊啊,被这大水题卡了一天(这是要填昨天的坑的博文),我果然还是太弱啊。
这么水的题,只用正反两遍BFS就好了,直接贴代码,一如既往地没有注释。
#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <cstring> 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 <int> 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 <int> 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 <int> 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; }