【bfs求助】不知道哪里错了诶
查看原帖
【bfs求助】不知道哪里错了诶
483928
Z1qqurat楼主2021/9/25 23:09

不知道怎么改,求大佬看看

#include <bits/stdc++.h>
using namespace std;
int n, a[200010], dis1[200010], dis2[200010], ans;
vector <int> Gragh[200010];

void bfs() {
	int cur;
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		q.push(i);
		if (i % 2 == 0) {
			dis2[i] = 0;
		} else {
			dis1[i] = 0;
		}
	}

	while (q.empty() == 0) {
		cur = q.front();
		q.pop();

		for (int i = 0; i < Gragh[cur].size(); i++) {
			int nxt = Gragh[cur][i];
			if (dis1[nxt] > dis2[cur] + 1) {
				dis1[nxt] = dis2[cur] + 1;
				q.push(nxt);
			}
			if (dis2[nxt] > dis1[cur] + 1) {
				dis2[nxt] = dis1[cur] + 1;
				q.push(nxt);
			}
		}
	}
}

int main() {
	memset(dis1, 0x3f, sizeof(dis1));
	memset(dis2, 0x3f, sizeof(dis2));

	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (i + a[i] >= 1 && i + a[i] <= n) {
			Gragh[i].push_back(i + a[i]);
		}
		if (i - a[i] >= 1 && i - a[i] <= n) {
			Gragh[i].push_back(i - a[i]);
		}
	}
	bfs();

	for (int i = 1; i <= n; i++) {
		if (i % 2 == 0) {
			ans = dis2[i];
		} else {
			ans = dis1[i];
		}

		if (ans == 0x3f3f3f3f) {
			cout << -1 << ' ';
		} else {
			cout << ans << ' ';
		}
	}
	return 0;
}
2021/9/25 23:09
加载中...