注意,存在错误解法可AC
查看原帖
注意,存在错误解法可AC
1260548
StevenYan楼主2025/1/20 01:23

AC之后对自己的解法都感觉不太自信,于是自造数据hack了一下 code

#include <bits/stdc++.h>
using namespace std;
#define maxn 10086
int n, m, s, t, ans = 0;
vector<int>p[maxn];
int vis[maxn] = {0}, stp[maxn], vis1[maxn] = {0};
vector<int>arcp[maxn];
queue<int>q;

void dfs(int x) {
	vis[x] = 1;
	for (int i = 0; i < arcp[x].size(); i++) {
		if (!vis[arcp[x][i]]) {
			dfs(arcp[x][i]);
		}
	}
}

void bfs(int x) {
	q.push(x);
	stp[x] = 0;
	while (!q.empty()) {
		int tmp = q.front();
		q.pop();
		if (tmp == t) {
			cout << stp[t];
			exit(0);
		}
		for (int i = 0; i < p[tmp].size(); i++) {
			if (vis1[p[tmp][i]] == 1) {
				q.push(p[tmp][i]);
				vis1[p[tmp][i]] = 0;
				stp[p[tmp][i]] = stp[tmp] + 1;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		if (x != y) {
			p[x].push_back(y);
			arcp[y].push_back(x);
		}
	}
	cin >> s >> t;
	dfs(t);
	for (int i = 1; i <= n; i++) {
		if (vis[i]) {
			vis1[i] = 1;
			for (int j = 0; j < p[i].size(); j++) {
				if (!vis[p[i][j]]) {
					vis1[i] = 0;
					break;
				}
			}
		}
	}
	if (vis1[s] != 1) {
		cout << "-1";
		return 0;
	}
	memset(stp, -1, sizeof(stp));
	bfs(s);
	return 0;
}
4 3
1 2
2 3
2 4
1 4

这组数据输入数据之后,什么也不会输出,纸上模拟了一遍也是发现会出现这个问题,提交上去却AC,具体原因已了解

但由此可以hack掉的一篇题解题解:P2296 [NOIP2014 提高组] 寻找道路

2025/1/20 01:23
加载中...