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 提高组] 寻找道路