题目描述

开启了升降梯的动力之后，探险队员们进入了升降梯运行的那条竖直的隧道，映入眼帘的是一条直通塔顶的轨道、一辆停在轨道底部的电梯、和电梯内一杆控制电梯升降的巨大手柄。

Nescafé 之塔一共有 $N$ 层，升降梯在每层都有一个停靠点。

手柄有 $M$ 个控制槽，第 $i$ 个控制槽旁边标着一个数 $C_i$，满足 $C_1 < C_2 < C_3 < \dots < C_M$。

如果 $C_i > 0$，表示手柄扳动到该槽时，电梯将上升 $C_i$ 层；如果 $C_i < 0$，表示手柄扳动到该槽时，电梯将下降 $-C_i$ 层；并且一定存在一个 $C_i = 0$，手柄最初就位于此槽中。

注意升降梯只能在 $1 \sim N$ 层间移动，因此扳动到使升降梯移动到 1 层以下、N 层以上的控制槽是不允许的。

电梯每移动一层，需要花费 $2$ 秒钟时间，而手柄从一个控制槽扳到相邻的槽，需要花费 $1$ 秒钟时间。

探险队员现在在 $1$ 层，并且想尽快到达 $N$ 层，他们想知道从 $1$ 层到 $N$ 层至少需要多长时间？

输入格式

第一行两个正整数 $N, M$。

第二行 $M$ 个整数 $C_1, C_2, \dots, C_M$。

输出格式

输出一个整数表示答案，即至少需要多长时间。

若不可能到达输出 $-1$。

样例

6 3
-1 0 2

19

样例解释

输入

$N=6$（共 6 层），$M=3$（3 个控制槽），$C = [-1, 0, 2]$

手柄初始在 $C_2=0$ 槽。

规则

• 电梯移动：每层 2 秒。
• 手柄扳动：每次移动到相邻槽花费 1 秒。

目标

从 1 层到 6 层。

分析

这是一个状态转移问题。状态为（当前楼层，当前手柄位置）。

设状态 $(floor, slot)$，其中 $floor \in [1,N]$，$slot \in [1,M]$。

初始状态：$(1, k)$，其中 $C_k = 0$（因为手柄初始在 0 槽）。

目标状态：$(N, any)$（到达第 N 层即可，不关心手柄位置）。

从状态 $(f, i)$ 可以转移到：

1. 扳动手柄到相邻槽：$(f, i \pm 1)$，花费 1 秒。
2. 扳动到槽 $i$ 后，按当前槽对应的 $C_i$ 移动电梯：新楼层 $f' = f + C_i$，必须满足 $1 \le f' \le N$。花费时间为移动楼层数 $\times 2$ 秒，即 $|C_i| \times 2$ 秒。注意：移动后手柄位置不变（因为只是扳到当前槽并触发移动）。

但注意：扳动手柄到相邻槽和移动电梯是两个独立操作，可以交替进行。

最短路模型

将每个状态看作节点，边权为操作时间，求从初始状态到任意 $(N, *)$ 的最短路。

因为 $N \le 1000$, $M \le 20$，状态数最多 $20000$，可以使用 Dijkstra 算法。

样例计算

初始状态：楼层 1，手柄在槽 2（因为 $C_2=0$）。

最优路径：

1. 从槽 2 扳到槽 3（花费 1 秒），然后按槽 3 上升 2 层（花费 4 秒），到达楼层 3。总 5 秒。
2. 从槽 3 扳到槽 2（花费 1 秒），然后按槽 2（$C=0$）不移动（花费 0 秒），无意义。 或者从槽 3 直接按槽 3 再上升 2 层到 5 层（花费 4 秒），总 9 秒，楼层 5。
3. 从槽 3 扳到槽 1（花费 2 秒），然后按槽 1 下降 1 层（花费 2 秒），到达楼层 4。总 13 秒。
4. 从槽 1 扳到槽 2（花费 1 秒），然后按槽 2（0）无变化。 或者从槽 1 直接按槽 1 再下降 1 层到 3 层，但已经去过。
5. 从槽 1 扳到槽 2（1 秒），再扳到槽 3（1 秒），然后按槽 3 上升 2 层到 6 层（4 秒），总 19 秒。

所以最短时间 19 秒。

数据范围

• $1 \le N \le 1000$
• $2 \le M \le 20$
• $-N < C_1 < C_2 < \dots < C_M < N$
• 保证存在 $C_i = 0$

算法分析

状态定义

设 $dist[f][i]$ 表示到达楼层 $f$ 且手柄在槽 $i$ 时的最短时间。

转移

从 $(f,i)$ 可以：

1. 扳动手柄到相邻槽 $i-1$ 或 $i+1$（如果存在），时间 $+1$，楼层不变。
2. 使用当前槽 $i$ 移动电梯：新楼层 $f' = f + C_i$，如果 $1 \le f' \le N$，则时间 $+ |C_i| \times 2$。

初始状态

找到 $i_0$ 使得 $C_{i_0} = 0$，则 $dist[1][i_0] = 0$。

目标

$\min_{i=1}^M dist[N][i]$。

如果所有 $dist[N][i]$ 均为无穷大，则输出 -1。

算法

使用 Dijkstra 算法求最短路。

状态数 $N \times M \le 20000$，边数：

• 每个状态最多 2 条扳动边（左右相邻槽）
• 1 条移动边（如果合法）

总边数约 $3 \times 20000 = 60000$，Dijkstra 复杂度 $O(E \log V)$，可行。

实现细节

• 使用优先队列（小根堆）优化 Dijkstra。
• 注意 $C_i$ 可能为负（下降）。
• 注意边界：楼层必须在 $[1,N]$。
• 注意可能存在无法到达的情况。

样例验证

对于样例，我们手动模拟 Dijkstra：

初始：$dist[1][2]=0$（因为 $C_2=0$）。

队列：$(0, (1,2))$

弹出 $(1,2)$：

• 扳到槽 1：$dist[1][1] = 0+1=1$。
• 扳到槽 3：$dist[1][3] = 0+1=1$。
• 移动：$C_2=0$，移动 0 层，无变化。

队列：$(1, (1,1))$, $(1, (1,3))$

弹出 $(1,1)$：

• 扳到槽 2：$dist[1][2]$ 已有 0，不更新。
• 移动：$C_1=-1$，移动到 0 层（非法），跳过。

弹出 $(1,3)$：

• 扳到槽 2：$dist[1][2]=0$，不更新。
• 移动：$C_3=2$，移动到 3 层，时间 $1+4=5$，$dist[3][3]=5$。

队列：$(5, (3,3))$

弹出 $(3,3)$：

• 扳到槽 2：$dist[3][2]=5+1=6$。
• 移动：$C_3=2$，移动到 5 层，时间 $5+4=9$，$dist[5][3]=9$。

队列：$(6, (3,2))$, $(9, (5,3))$

弹出 $(3,2)$：

• 扳到槽 1：$dist[3][1]=6+1=7$。
• 扳到槽 3：$dist[3][3]=5$，不更新。
• 移动：$C_2=0$，无变化。

弹出 $(5,3)$：

• 扳到槽 2：$dist[5][2]=9+1=10$。
• 移动：$C_3=2$，移动到 7 层（非法），跳过。

弹出 $(3,1)$：

• 扳到槽 2：$dist[3][2]=6$，不更新。
• 移动：$C_1=-1$，移动到 2 层，时间 $7+2=9$，$dist[2][1]=9$。

弹出 $(5,2)$：

• 扳到槽 1：$dist[5][1]=10+1=11$。
• 扳到槽 3：$dist[5][3]=9$，不更新。
• 移动：$C_2=0$，无变化。

弹出 $(2,1)$：

• 扳到槽 2：$dist[2][2]=9+1=10$。
• 移动：$C_1=-1$，移动到 1 层，时间 $9+2=11$，$dist[1][1]=1$，不更新。

弹出 $(5,1)$：

• 扳到槽 2：$dist[5][2]=10$，不更新。
• 移动：$C_1=-1$，移动到 4 层，时间 $11+2=13$，$dist[4][1]=13$。

弹出 $(4,1)$：

• 扳到槽 2：$dist[4][2]=13+1=14$。
• 移动：$C_1=-1$，移动到 3 层，时间 $13+2=15$，$dist[3][1]=7$，不更新。

弹出 $(4,2)$：

• 扳到槽 1：$dist[4][1]=13$，不更新。
• 扳到槽 3：$dist[4][3]=14+1=15$。
• 移动：$C_2=0$，无变化。

弹出 $(4,3)$：

• 扳到槽 2：$dist[4][2]=14$，不更新。
• 移动：$C_3=2$，移动到 6 层，时间 $15+4=19$，$dist[6][3]=19$。

到达 6 层，时间 19。

所以输出 19。

总结

本题是状态空间搜索（最短路）问题，关键是将楼层和手柄位置组合成状态，然后用 Dijkstra 求最短时间。注意状态转移的合法性（楼层范围）和操作时间计算。