bfs,50 TLE+MLE 求助
查看原帖
bfs,50 TLE+MLE 求助
635829
D_FANG楼主2022/9/29 18:32
#include<bits/stdc++.h>
using namespace std;
int n,start,e;
int a[210];
bool vis[210];
int ans;
queue<pair<int,int> >q;
void bfs(int st){
	int f=0;
	q.push(make_pair(st,0));
	while (!q.empty()){
		int x=q.front().first;
		int y=q.front().second;
		q.pop();
		int xx=x+a[x];
		if (xx==e){
			ans=y+1;
			return ;
		}
		if (xx>0&&xx<=n&&vis[xx]==false){
			f=1;
			q.push(make_pair(xx,y+1));
		}
		xx=x-a[x];
		if (xx==e){
			ans=y+1;
			return ;
		}
		if (xx>0&&xx<=n&&vis[xx]==false){
			q.push(make_pair(xx,y+1));
			f=1;
		}
		if (f==0){
			vis[x]=true;
		}
	}
}
int main(){
	cin>>n>>start>>e;
	for (int i=1;i<=n;i++){
		cin>>a[i];
	}
	if (start==e){
		cout<<0;
		return 0;
	}
	bfs(start);
	if (ans!=0)
	cout<<ans;
	else{
		cout<<-1;
	}
	return 0;
} 
2022/9/29 18:32
加载中...