#9 #11 TLE求调
查看原帖
#9 #11 TLE求调
1088732
GXZJQ楼主2024/7/18 21:03
/**
 * 题目名称:P2296 [NOIP2014 提高组] 寻找道路
 * 题目链接:https://www.luogu.com.cn/problem/P2296
 * 做题时间:2024年7月18日
 * 考查内容:搜索,最短路
 * 难度评级:普及+/提高
 * 主要思路:
 * Step 1:将边反着建,这样子可以使用BFS看终点可以到达那些点
 * Step 2:枚举所有的点,如果这个点没有被标记,那么看它出边指向的点有没有被标记,如果被标记了,这个标记也是不合法的,可以通过条件一的反条件判断
 * Step 3:对于所有合法的点进行单源最短路即可
 * 注意事项:
 **/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e4 + 10;
int n, m, s, t;
int h[maxn], nxt[maxn], to[maxn], cnt;
int dis[maxn];
bool vis[maxn], point[maxn];
queue<int> q;

//快读
int read() {
	int x = 0, y = 1;
	char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '0')y = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * y;
}

//链式前向星加边
void add(int a, int b) {
	to[++cnt] = b;
	nxt[cnt] = h[a];
	h[a] = cnt;
}

//搜索终点能抵达的点的编号
void BFS() {
	vis[t] = true;
	q.push(t);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = h[u]; i != -1; i = nxt[i]) {
			int v = to[i];
			if (!vis[v]) vis[v] = true, q.push(v);
		}
	}
}

//最终记录合法点
void check() {
	memcpy(point, vis, sizeof vis);
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			for (int j = h[i]; ~j; j = nxt[j]) {
				int v = to[j];
				if (point[v]) point[v] = false;
			}
		}
	}
}

//求出最短路径
void Solve() {
	q.push(t);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = h[u]; i != -1; i = nxt[i]) {
			int v = to[i];
			if (point[v]) {
				point[v] = false;
				q.push(v);
				dis[v] = dis[u] + 1;
				if (v == s) return;
			}
		}
	}
}

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	memset(h, -1, sizeof h);
	n = read(), m = read();
	for (int i = 1; i <= m; i++) {
		int x, y;
		x = read(), y = read();
		if (x == y) continue;
		add(y, x);
	}
	s = read(), t = read();
	BFS();
	check();
	if (!point[s]) cout << "-1", exit(0);
	Solve();
	cout << dis[s];
	return 0;
}
2024/7/18 21:03
加载中...