1 条题解

  • 0
    @ 2024-11-2 21:48:18

    AA 开始,搜索每一条路,可以更新答案再继续搜索,不然会搜索多余导致 TLETLE。 时间复杂度 O(n2)O(n^2)

    #include<bits/stdc++.h>
    using namespace std;
    int n,a,b,k[201],dis[201];
    void dfs(int node,int step){
    	dis[node]=step;//一定可以更新
    	int v=node-k[node];
    	if(1<=v&&step+1<dis[v]/*可以更新在搜索*/)//下
    		dfs(v,step+1);
    	v=node+k[node];
    	if(v<=n&&step+1<dis[v])//上
    		dfs(v,step+1);
    	return;
    }
    int main(){
    	memset(dis,0x3f,sizeof(dis));
    	cin>>n>>a>>b;
    	for(int i=1;i<=n;i++)
    		cin>>k[i];
    	dfs(a,0);
    	cout<<(dis[b]==0x3f3f3f3f?-1:dis[b]);
    	return 0;
    }
    
    • 1

    信息

    ID
    127
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    50
    已通过
    24
    上传者