求助,请问一下链式前向星+dfs为什么t 了
查看原帖
求助,请问一下链式前向星+dfs为什么t 了
672837
DaShabby楼主2023/1/17 17:15
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=2e4+34;
int inf=0x3f3f3f3f;
int vis[maxn],idx,cnt,tot,step[maxn];
int head[maxn],nex[maxn],to[maxn];
vector<int>G[maxn];
void add(int u,int v){
	nex[++tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}
void dfs(int u){
	for(int i=head[u];i;i=nex[i]){
		int v=to[i];
		if(vis[v])continue;
		step[v]=min(step[v],step[u]+1);
		vis[v]++;
		dfs(v);
		vis[v]--;
	}
}
void work(){
	int n,a,b,x;
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<=n;i++){
		step[i]=inf;
		scanf("%d",&x);
		if(!x)continue;
		if(1<=i+x&&i+x<=n)add(i,i+x);
		if(1<=i-x&&i-x<=n)add(i,i-x);
	}
	step[a]=0;
	vis[a]++;
	dfs(a);
	printf(step[b]==inf?"-1\n":"%d\n",step[b]);
}
int main()
{
    work();
    return 0;
}```
2023/1/17 17:15
加载中...