[NOIP2014]寻找道路

解题报告

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

 

发表回复

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据