思路

考虑 Dijkstra 并建分层图。

对于每个控制槽 $C_i$ ，新开一层点，在保证不越界的情况下由第 $j$ 个点向第$j - C_i$ 个点连一条权值为 $2 \times \lvert C_i \rvert $ 的单向边。

对于每两个控制槽之间，由下层每一点向上层对应的该点连一条权值为 $1$ 的双向边。

然后跑一遍 Dijkstra 并对每层第 $n$ 点的 $dist$ 求 $min$ 即可。

code

#include<bits/stdc++.h>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N=20010,M=60010,INF=0x3f3f3f3f;
int n,m;
int c[N];
int h[N],e[M],w[M],ne[M],idx;
int dist[N];
bool st[N];
int flag;
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1+n*(flag-1)]=0;
    priority_queue<PII,vector<PII>,greater<PII> > heap;
    heap.push({0,1+n*(flag-1)});
    while(heap.size())
    {
        PII t=heap.top();
        heap.pop();
        int ver=t.second,distance=t.first;
        if(st[ver]) continue;
        st[ver]=true;
        for(int i=h[ver];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>distance+w[i])
            {
                dist[j]=distance+w[i];
                heap.push({dist[j],j});
            }
        }
    }
    int res=INF;
    for(int i=n;i<=n*m;i+=n) res=min(res,dist[i]);
    if(res==INF) return -1;
    else return res;
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    memset(h,-1,sizeof h);
    cin>>c[1];
    if(!c[1]) flag=1;
    for(int i=1;i<=n;i++)
    {
        if(c[1]&&i+c[1]>=1&&i+c[1]<=n) add(i,i+c[1],2*abs(c[1]));
    }
    for(int i=2;i<=m;i++)
    {
        cin>>c[i];
        if(!c[i]) flag=i;
        for(int j=1+n*(i-1);j<=n*i;j++)
        {
            if(c[i]&&j-n*(i-1)+c[i]>=1&&j-n*(i-1)+c[i]<=n) add(j,j+c[i],2*abs(c[i]));
            add(j-n,j,1),add(j,j-n,1);
        }
    }
    cout<<dijkstra();
    return 0;
}