mle求解
查看原帖
mle求解
1122530
elpsconr楼主2024/4/3 01:25

为啥我并在一起循环就会mle,其中有个点tle,分开写就能ac?

mle,tle版:

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,a,b,arr[N],dis[N];
int d[]={1,-1};
void dfs(int x,int step)
{
    dis[x]=step;
    for(int i=0;i<2;++i)
    {
        int xx=x+d[i]*arr[x];
        if(xx<1||xx>n||step>dis[xx]) continue;
        dfs(xx,step+1);
    }
}
int main()
{
    memset(dis,0x3f,sizeof dis);
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++) cin>>arr[i];
    dfs(a,0);
    cout<<((dis[b]==0x3f3f3f3f)?-1:dis[b])<<endl;
    return 0;
}

正常ac版:

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,a,b,arr[N],dis[N];
int d[]={1,-1};
void dfs(int x,int step)
{
    dis[x]=step;
    int xx=x+arr[x];
    if(xx>=1&&xx<=n&&step+1<dis[xx])
    dfs(xx,step+1);
    xx=x-arr[x];
    if(xx>=1&&xx<=n&&step+1<dis[xx])
    dfs(xx,step+1);
}
int main()
{
    memset(dis,0x3f,sizeof dis);
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++) cin>>arr[i];
    dfs(a,0);
    cout<<((dis[b]==0x3f3f3f3f)?-1:dis[b])<<endl;
    return 0;
}
2024/4/3 01:25
加载中...