dfs#1TLE求助
查看原帖
dfs#1TLE求助
648868
zjhdbc楼主2023/8/14 20:19
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,a[50005],ans=INT_MAX,b,v;
ll c[50005];
void dfs(ll now,ll sum)
{
	if(now==b)
	{
		ans=min(ans,sum);
	}
	else if(sum<=ans)
	{
		c[now]=1;
		if(now+a[now]<=n and c[now+a[now]]==0) 
		{
			dfs(now+a[now],sum+1);
		}
		if(now-a[now]>=1 and c[now-a[now]]==0)
		{
			dfs(now-a[now],sum+1);
		}
		c[now]=0;
	}
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>v>>b;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	c[v]=1;
	dfs(v,0);
	if(ans!=INT_MAX)
	{
		cout<<ans;
	}
	else
	{
		cout<<"-1";
	}
	return 0;
}
2023/8/14 20:19
加载中...