时间限制：1秒

空间限制：32768K
n 个小区排成一列，编号为从 0 到 n-1 。一开始，美团外卖员在第0号小区，目标为位于第 n-1 个小区的配送站。
给定两个整数数列 a[0]~a[n-1] 和 b[0]~b[n-1] ，在每个小区 i 里你有两种选择：
1) 选择a：向前 a[i] 个小区。
2) 选择b：向前 b[i] 个小区。

把每步的选择写成一个关于字符 ‘a’ 和 ‘b’ 的字符串。求到达小区n-1的方案中，字典序最小的字符串。如果做出某个选择时，你跳出了这n个小区的范围，则这个选择不合法。
• 当没有合法的选择序列时，输出 “No solution!”。
• 当字典序最小的字符串无限长时，输出 “Infinity!”。
• 否则，输出这个选择字符串。

字典序定义如下：串s和串t，如果串 s 字典序比串 t 小，则
• 存在整数 i ≥ -1，使得∀j，0 ≤ j ≤ i，满足s[j] = t[j] 且 s[i+1] < t[i+1]。
• 其中，空字符 < ‘a’ < ‘b’。
输入描述:

输入有 3 行。

第一行输入一个整数 n (1 ≤ n ≤ 10^5)。

第二行输入 n 个整数，分别表示 a[i] 。

第三行输入 n 个整数，分别表示 b[i] 。

−n ≤ a[i], b[i] ≤ n

输出描述:

输出一行字符串表示答案。

解法： 

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
vector <int> G[maxn];
int n, a[maxn], b[maxn];
bool vis1[maxn], vis2[maxn];
string s;
void bfs(int x){
    queue <int> q;
    q.push(x);
    vis1[x] = 1;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i=0; i<G[u].size(); i++){
            int v = G[u][i];
            if(!vis1[v]){
                vis1[v] = 1;
                q.push(v);
            }
        }
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
        int u = i+a[i];
        if(u>=1&&u<=n){
            G[u].push_back(i);
        }
    }
    for(int i=1; i<=n; i++){
        scanf("%d", &b[i]);
        int u = i+b[i];
        if(u>=1&&u<=n){
            G[u].push_back(i);
        }
    }
    bfs(n);
    vis2[1]=1;
    bool flag = 0;
    for(int x=1; x!=n&&!flag;){
        int nxt = x+a[x];
        if(nxt>=1&&nxt<=n&&vis1[nxt]){
            if(!vis2[nxt]){
                vis2[nxt]=1;
                s+='a';
            }
            else{
                flag = 1;
            }
            x = nxt;
        }
        else{
            nxt = x+b[x];
            if(nxt>=1&&nxt<=n&&vis1[nxt]){
                if(!vis2[nxt]){
                    vis2[nxt]=1;
                    s+='b';
                }
                else{
                    flag=1;
                }
                x=nxt;
            }
            else{
                puts("No solution!");
                return 0;
            }
            x = nxt;
        }
    }
    if(flag) puts("Infinity!");
    else cout<<s<<endl;
    return 0;
}