题面见COGS
啊啊啊啊啊啊啊啊啊，被这大水题卡了一天（这是要填昨天的坑的博文），我果然还是太弱啊。
这么水的题，只用正反两遍BFS就好了，直接贴代码，一如既往地没有注释。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
#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; } |