[NOIP2014]寻找道路

解题报告

题面见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;
}

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理