题解 | #变化的飞行棋#

暴力的建出循环$mm$次的飞行器图，长度$n\times m\le 5e6n\; \backslash times\; m\; \backslash leq\; 5e6$，

之后考虑每个点$ii$处能一次跳到的位置共有$1212$个，即筛子数为$j\in [1,6]j\; \backslash in\; [1,\; 6]$直接走到$i+ji\; +\; j$ 处后选择不走，或者

走到$i+ji\; +\; j$处后继续选择走$a_{i+j}a\_\{i\; +\; j\}$步，即一步内共$1212$种走法:$j\in [1,6],i+jj\; \backslash in\; [1,\; 6],\; ~i\; +\; j$ 和 $i+j+a_{i+j}~i\; +\; j\; +\; a\_\{i\; +\; j\}$，考虑边数上限为$n\times m\times 12\le 6e7n\; \backslash times\; m\; \backslash times\; 12\; \backslash leq\; 6e7$条，时间复杂度还算可以，所以直接从起点跑$bfsbfs$即可，但是注意的是不能真的把图建出来，我建图跑了一发MLE，因为每个点$ii$的边都是固定的$1212$条直接$bfsbfs$过程中扩展就行了。

总时间复杂度$O(nm)O(nm)$。

const int N = 5e6 + 10, M = 1e4 + 10;

int a[N];
int dis[N];
int b[M];
int n, m;

void bfs()
{
    queue<int> que;
    que.push(1);
    dis[1] = 0;
    while(!que.empty())
    {
        int u = que.front(); que.pop();
        for(int i = 1;i <= 6;i ++)
        {
            int v = min(n * m + 1, u + i);
            if(dis[v] > dis[u] + 1)
            {
                dis[v] = dis[u] + 1;
                que.push(v);
            }
            v = min(n * m + 1, u + i + a[u + i]);
            if(dis[v] > dis[u] + 1)
            {
                dis[v] = dis[u] + 1;
                que.push(v);
            }
        }
    }
}

void solve(int Case)
{
    n = read(), m = read();
    for(int i = 1;i <= n;i ++) a[i] = read();
    for(int i = 1;i <= n;i ++) b[i] = read();
    for(int i = n + 1;i <= n * m;i ++)
        a[i] = a[i - n] + b[(i - 1) %  n + 1];

    for(int i = 1;i <= n * m + 1;i ++) dis[i] = inf;

    bfs();
    printf("%lld\n", dis[n * m + 1]);
}

signed main()
{
//    ios;
    int t = 1;// t = read();
    for(int i = 1;i <= t;i ++) solve(i);
    return 0;
}