https://www.luogu.org/problem/show?pid=T2483
题目背景
开启了升降梯的动力之后，探险队员们进入了升降梯运行的那条竖直的隧道，映入眼帘的是一条直通塔顶的轨道、一辆停在轨道底部的电梯、和电梯内一杆控制电梯升降的巨大手柄。
题目描述
Nescafe 之塔一共有N 层，升降梯在每层都有一个停靠点。手柄有M个控制槽，第i 个控制槽旁边标着一个数Ci，满足C1<C2<C3<⋯⋯<CM。如果Ci>0，表示手柄扳动到该槽时，电梯将上升Ci 层；如果Ci<0，表示手柄扳动到该槽时，电梯将下降-Ci 层；并且一定存在一个Ci=0，手柄最初就位于此槽中。注意升降梯只能在1到N 层间移动，因此扳动到使升降梯移动到1 层以下、N 层以上的控制槽是不允许的。
电梯每移动一层，需要花费2 秒钟时间，而手柄从一个控制槽扳到相邻的槽，需要花费1 秒钟时间。探险队员现在在1 层，并且想尽快到达N 层，他们想知道从1 层到N 层至少需要多长时间？
输入输出格式
输入格式：
第一行两个正整数 N、M。
第二行M 个整数C1、C2⋯⋯CM。
输出格式：
输出一个整数表示答案，即至少需要多长时间。若不可能到达输出-1。
输入输出样例
6 3
-1 0 2
19
说明
对于30% 的数据，满足1≤N≤ 10; 2≤M≤ 5。
对于100% 的数据，满足1≤N≤1000; 2 ≤ M ≤20;-N < C1 <C2 < …… < CM < N。
样例解释
手柄从第二个槽扳到第三个槽（0 扳到2），用时1 秒，电梯上升到3层，用时4 秒。
手柄在第三个槽不动，电梯再上升到5 层，用时4 秒。
手柄扳动到第一个槽（2 扳到-1），用时2 秒，电梯下降到4 层，用时2 秒。
手柄扳动到第三个槽（-1 扳倒2），用时2 秒，电梯上升到6 层，用时4 秒。
总用时为(1+4)+4+(2+2)+(2+4)=19 秒。
转换成图。把每次扳动看成是路径。spfa方程
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define M 400001
#define N 25001
queue<int>q;
int n,m,a[],en,v[M],w[M],first[M],nex[M],num[][],sta,ans=,dis[N];
bool inq[N];
int Abs(const int &x){return x< ? (-x) : x;}
void AddEdge(const int &U,const int &V,const int &W)
{
v[++en]=V;
w[en]=W;
nex[en]=first[U];
first[U]=en;
}
void spfa(const int &s)
{
memset(dis,0x7f,sizeof(dis));
q.push(s); inq[s]=; dis[s]=;
while(!q.empty())
{
int U=q.front();
for(int i=first[U];i;i=nex[i])
if(dis[v[i]]>dis[U]+w[i])
{
dis[v[i]]=dis[U]+w[i];
if(!inq[v[i]])
{
inq[v[i]]=;
q.push(v[i]);
}
}
q.pop(); inq[U]=;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++) scanf("%d",&a[i]);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
num[i][j]=++en;
if(i==&&a[j]==) sta=en;
} en=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)//单层移动手柄
for(int k=;k<=m;k++)
if(j!=k)
AddEdge(num[i][j],num[i][k],Abs(j-k));
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(a[j]!=&&i+a[j]>=&&i+a[j]<=n)
AddEdge(num[i][j],num[i+a[j]][j],(Abs(a[j])<<));
spfa(sta);
for(int i=;i<=m;i++) ans=min(ans,dis[num[n][i]]);
printf("%d\n",ans>= ? - : ans);
return ;
}