题解 | #送外卖#

这道题用深搜可以，广搜也行

先找到所以可达的点，反向建图即可

然后从起点扩展，注意是字典序最短，而不是路径最短

在扩展的过程中，如果点没走过并且可达则加入队列，这个时候就可以直接break掉了

因为对于当前可达的点来说一定可达

是按照字典序走的

如果发现某个点的扩展点是遍历过的并且是可达的，那么存在一个循环

否则一定可以得到答案

这里要求记录答案，直接用前项链表即可

#include<bits/stdc++.h>
using namespace std;
#define maxm 100010
int vis[maxm],st[maxm];
vector<int>G[maxm];
vector<int>T[maxm];
pair<int,int> pre[maxm];
int n;
char oper[]={'a','b'};
vector<int>inx[maxm];
int bfs(int type){
    if(type==0){
        queue<int>q;
        q.push(n-1);
        st[n-1]=1;
        while(q.empty()==false){
            int u=q.front();q.pop();
            for(int i=0;i<(int)T[u].size();i++){
                int v=T[u][i];
                if(st[v]) continue;
                st[v]=1;
                q.push(v);
            }
        }
        if(st[0]) return 1;
        return 0;
    }
    memset(pre, -1, sizeof pre);
    queue<int>q;
    q.push(0);
    vis[0]=1;
    while(q.empty()==false){
        int u=q.front();q.pop();
        if(u==n-1) {
            return 1;
        }
       
        for(int i=0;i<(int)G[u].size();i++){
            int v=G[u][i];
            if(vis[v]){
                if(st[v]) return 0;
                continue;
            }
            if(st[v]==0) continue;
            vis[v]=1;
            q.push(v);
            pre[v]={u,inx[u][i]};
            break;    
        }
        
    }
    return 0;
}
int main(){
    
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        if(x+i>=0&&x+i<n) {
            G[i].push_back(x+i);
            
            T[x+i].push_back(i);
            inx[i].push_back(0);
        }
    }
    for(int i=0;i<n;i++) {
        int x;
        cin>>x;
        if(x+i>=0&&x+i<n){
            G[i].push_back(x+i);
            T[x+i].push_back(i);
            inx[i].push_back(1);
        }
    }
    if(bfs(0)==0) cout<<"No solution!\n";
    else {
        if(bfs(1)==0) cout<<"Infinity!\n";
        else {
            string str;
//             cout<<pre[n-1].first;
            for(int i=n-1;i!=0;i=pre[i].first){
                str+=oper[pre[i].second];
            }
//             cout<<str.size()<<str;
            for(int i=str.size()-1;i>=0;i--) cout<<str[i];
        }
    }
    return 0;
}