苣蒻在第十个点TLE了,求助大佬
查看原帖
苣蒻在第十个点TLE了,求助大佬
648772
Liyuqiao11楼主2023/7/12 12:55

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
int n,a[N],b[N],vis[N],dis[N],mp[N],f[N],cnt,f_2[N];
struct S{
    int m;
    int step;
};
bool bfs(int x){
    queue<S> q;
    q.push(S{x,0});
    vis[x]=1;
    dis[x]=0;
    while(!q.empty()){
        int u=q.front().m,t=q.front().step;
        q.pop();    
        if(u-a[u]<=0){
            cout<<t+1<<endl;
            cnt=t+1;
            f[0]=0;
            f_2[0]=u;
            return true;
        }
        for(int i=1;i<=min(a[u],u);i++){
            int z=u-i+b[u-i];
            if(t+1>=dis[z]&&vis[z]==1) continue;
            vis[z]=1;
            dis[z]=t+1;
            f[z]=u-i;
            f_2[z]=u;
            q.push(S{z,t+1});
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    bool dc=bfs(n);
    if(!dc){
        cout<<-1<<endl;
    }
    else{
        int tot=0,l=0;
        while(tot<cnt){
            mp[++tot]=f[l];
            l=f_2[l];
        }
        for(int i=tot;i>=1;i--){
            cout<<mp[i]<<" ";
        }
    }
    return 0;
}
2023/7/12 12:55
加载中...