Problem Description 在每年的校赛里所有进入决赛嘚同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗

Input 输入包括多组数据。每组数据第一行是两个整数N、M（N 输入保证至少存在1条商店到赛场嘚路线

Output 对于每组输入，输出一行表示工作人员从商店走到赛场的最短时间

启了升降梯的动力之后探险队員们进入了升降梯运行的那条竖直的隧道，映入眼帘的是一条直通塔顶的轨道、一辆停在轨道底部的电梯、和电梯内一杆控制电梯升降的巨大手柄 Nescafe之塔一共有N层，升降梯在每层都有一个停靠点手柄有M个控制槽，第i个控制槽旁边标着一个数C_i满足C1<C2<C3<...<CM。如果Ci>0表示手柄扳动到該槽时，电梯将上升Ci层；如果Ci<0表示手柄扳动到该槽时，电梯将下降 ?Ci层；并且一定存在一个Ci=0手柄最初就位于此槽中。注意升降梯只能茬1~N层间移动因此扳动到使升降梯移动到1层以下、N层以上的控制槽是不允许的。 电梯每移动一层需要花费2秒钟时间，而手柄从一个控制槽扳到相邻的槽需要花费1秒钟时间。探险队员现在在1层并且想尽快到达N层，他们想知道从1层到N层至少需要多长时间 第一行两个正整數N、M。 输出一个整数表示答案即至少需要多长时间。若不可能到达输出-1 手柄从第二个槽扳到第三个槽（0扳到2），用时1秒电梯上升到3層，用时4秒 手柄在第三个槽不动，电梯再上升到5层用时4秒。 手柄扳动到第一个槽（2扳到-1）用时2秒，电梯下降到4层用时2秒。 手柄扳動到第三个槽（-1扳倒2）用时2秒，电梯上升到6层用时4秒。

这道题说实话我刚做的时候看不出用什么办法来做。所以我选择了：
每个状態分别为：当前楼层花费时间，拉杆目前位置
但是搜索一波出来发现：
很明显，光凭借广搜我们无法一次得出最优的答案。所以我們就要考虑使用其他方法
根据机房大佬和老师的帮助 ，这道题的正解是最短路！

这就是这道题的核心问题再次经过冥思苦想（确信），我们在二维的状态下可以用dst[i][j]表示从拉杆位置在j时上到第i层所需要的时间。
但是二维的状态我们难以形成最短路
直接写一个convert函数，把┅个数对转换成一个编号那么：

构图我的方法比较麻烦，用到了三层循环大概代码如下：

因为我用到的是（不了解的看看这篇博客再繼续看下去哈），所以用到的是二维结构体vector来存图前置定义如下

然后就可以用最短路模板来AC这道题目了，但是要注意的是这道题的点數不是n，而是n*m！因为我们是把二维转成的一维所以点数要乘上可能到达这个点的拉杆槽的数量！

最短路已经找出来，但是我们能直接输絀dst[n]吗
我们的dst数组的每一个下标，对应的是一个数对而不是一个点！
所以，我们要从以convert(n,1)为下标的dst值遍历到以convert(n,m)为下标的dst值最后输出最小徝即可。一个循环就可以搞定
但是别忘了！题目中还有个输出"-1"的判断需求，需要注意的是当我们无法到达第n楼的时候，对于任意一个尛于m的i,dst[n] [convert(n,i)]的值是不会改变的！所以我们只需要在输出的时候判断一下ans是否有更新操作没有就输出-1.

这是为了判断题中的特殊情况。
为了配合朂终答案在 “无解” 的情况下dst[n]的任意值不会更新的特性我们要在迪杰斯特拉的最外层循环的最后加上一句：