题解 | #送外卖#

解题思路：如果用bfs从下标为0每次移动至另一状态判断是否能到达终点，其实现难点在于如何判断是否会Infinity，因为不同的走法其路线不同走过的顶点也不同；用dfs+回溯可以AC ；用bfs求解思路：反向建图，从下标n-1(实现时下标从1-n)判断是否有到达0的路径，在经过的节点上标记。接着从下标为0每次判断下一步是否在可行路径的节点上，且如果重复
到达同一节点则Infinity。
实现代码：

#include<iostream>
#include<string> 
#include<vector>
#include<queue>
using namespace std;

const int Max_N = 1e5+10;

int n;
int a[Max_N], b[Max_N];
vector<int> graph[Max_N];
bool visited1[Max_N], visited2[Max_N]; //反向、正向经过的节点 

void bfs(int s);
void solve();

int main()
{
    cin>>n;
    for( int i=1; i<=n; i++ )
    {
        cin>>a[i];
        int x = i + a[i];
        if( 1<=x&&x<=n )    graph[x].push_back(i);//反向建图 
    }
    for( int i=1; i<=n; i++ )
    {
        cin>>b[i];
        int x = i + b[i];
        if( 1<=x&&x<=n )    graph[x].push_back(i);//反向建图 
    }

    solve();

    return 0;
}

void bfs(int s)
{
    queue<int> que;
    que.push(s);
    visited1[s] = true; //先true在push 防止超时 
    while( !que.empty() )
    {
        int v = que.front(); que.pop();//v 当前节点 
        int cize = graph[v].size();
        for( int i=0; i<cize; i++ )
        {
            int u = graph[v][i];
            if( !visited1[u] )
            {
                visited1[u] = true;
                que.push(u);    //可行路径上的节点 
            }    
        }    
    }    
}

void solve()
{
    bfs(n);

    if( !visited1[1] ) //没有从n到1的路径 
    {
        cout<<"No solution!"<<endl;
        return;
    }

    bool infinity = false;
    string ans = "";
    int x = 1;
    while( x!=n )
    {
        int nx = x + a[x];
        if( 1<=nx&&nx<=n && visited1[nx] )
        {
            if( !visited2[nx] )
            {//没有重复(环路) 
                visited2[nx] = true;
                ans += "a";
                x = nx;
            }
            else//重复路径 
                infinity = true;
        }
        else
        {
            nx = x + b[x];
            if( 1<=nx&&nx<=n && visited1[nx] )//可以走 
            {
                if( !visited2[nx] )
                {//没有重复(环路) 
                    visited2[nx] = true;
                    ans += "b";
                    x = nx;
                }
                else
                    infinity = true;
            }
        }
        if( infinity )    break;
    }
    if( infinity )    cout<<"Infinity!"<<endl;
    else            cout<<ans<<endl;
}