送外卖

思路(反向建图+bfs)

注意本题所求的是最小字典序的字符串，而不是最小长度的字符串，所以需要反向建图，求出 $s t a t e [i] = t r u e$ 表示点 $i$ 可以到达点 $n$ (反向建图的bfs1函数中结点编号1-n，求最小字典序的bfs函数中结点编号0~n-1)。
反向建图计算完state数组后, 进行普通的bfs。 ①如果选择a数组走到aa并且 $s t a t e [a a + 1] = t r u e$ ，那么必选走a数组的结果aa入队, 不考虑b数组；②当aa不能到达终点时，若b可以到达，则选择走b数组的结果bb入队；两个条件都不满足，不考虑当前出队结点，考虑下一个出队结点。
当选择a或者选择b走到终点时，返回1，代表有解；当选择a走到aa(或者选择b走到bb)，但是 $s t [a a] = = t r u e (或者 s t [b b] = = t r u e)$ ，表示aa(或者bb)已经入过队了，则返回0，表示 $I n f i n i t y$ ；上述两种情况都不满足，最后返回-1，表示 $No\ Solution$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1};
const double eps = 1e-6;
const int N = 1e5 + 10, M = 2 * N;
int n, m;
int a[N], b[N];
bool st[N], state[N];
int h[N], e[M], ne[M], idx;

unordered_map<int, pair<char, int>> pre;

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    // w[idx] = c;
    h[a] = idx++;
}

void bfs1()
{
    queue<int> q;
    q.push(n);
    state[n] = true;

    while (!q.empty())
    {
        int t = q.front();
        q.pop();

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            if (state[j])
                continue;
            state[j] = true;
            q.push(j);
        }
    }
}



int bfs()
{
    memset(st, 0, sizeof st);
    queue<int> q;
    st[0] = true;
    q.push(0);

    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        int aa = t + a[t], bb = t + b[t];

        // 这段注释打开和不打开都可以AC
//         // No Solution
//         if ((aa < 0 || aa > n - 1) && (bb < 0 || bb > n - 1) && q.empty())
//             return -1;

        if (aa <= n - 1 && aa >= 0 && state[aa + 1])
        {
            // Infinity
            if (st[aa])
                return 0;

            q.push(aa);
            pre[aa].first = 'a';
            pre[aa].second = t;
            st[aa] = true;
            if (aa == n - 1)
                return 1;
        }
        else if (bb <= n - 1 && bb >= 0 && state[bb + 1])
        {
            // Infinity
            if (st[bb])
                return 0;

            q.push(bb);
            pre[bb].first = 'b';
            pre[bb].second = t;
            st[bb] = true;
            if (bb == n - 1)
                return 1;
        }
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        int aa = i + 1 + a[i];
        if (aa >= 1 && aa <= n)
            add(aa, i + 1);
    }
    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
        int bb = i + 1 + b[i];
        if (bb >= 1 && bb <= n)
            add(bb, i + 1);
    }
    bfs1();

    int t = bfs();
    if (t == -1)
        cout << "No solution!";
    else if (t == 1)
    {
        vector<char> ans;
        for (int i = n - 1; i != 0; i = pre[i].second)
        {
            ans.push_back(pre[i].first);
        }
        for (int i = ans.size() - 1; i >= 0; i--)
        {
            cout << ans[i];
        }
    }
    else
        cout << "Infinity!";
    return 0;
}

题解 | #送外卖#

送外卖

思路(反向建图+bfs)

代码