Description：
开启了升降梯的动力之后，探险队员们进入了升降梯运行的那条竖直的隧道，映入眼帘的是一条直通塔顶的轨道、一辆停在轨道底部的电梯、和电梯内一杆控制电梯升降的巨大手柄。
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 层至少需要多长时间？
Input：
第一行两个正整数 N、M。
第二行 M 个整数 C1、C2„„CM。
Output：
输出一个整数表示答案，即至少需要多长时间。若不可能到达输出-1
思路：水题，将每一层的每个状态拆开连边，然后建一个超级源点与终点，连边即可
#include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<cmath> using namespace std; const int N = 30010, M = 1e6 + 10, INF = 1e9; typedef pair<int,int> P; int head[N], now; struct edges{ int to, next, w; }edge[M<<1]; void add(int u,int v, int w){ edge[++now] = {v, head[u], w}; head[u] = now;} int n, m, c[N], dis[N]; int id(int x,int y){ return (x - 1) * m + y;} void dij(int s){ priority_queue<P,vector<P>, greater<P> > heap; memset(dis,0x3f, sizeof(dis)); dis[s] = 0; heap.push(P(0, s)); while(!heap.empty()){ P tmp = heap.top(); heap.pop(); int x = tmp.second; if(tmp.first > dis[x]) continue; for(int i = head[x]; i; i = edge[i].next){ int v = edge[i].to; if(dis[v] > dis[x] + edge[i].w){ dis[v] = dis[x] + edge[i].w; heap.push(P(dis[v], v)); } } } return ; } int main(){ scanf("%d%d",&n, &m); int pos; for(int i = 1; i <= m; i++){ scanf("%d",&c[i]); if(c[i] == 0) pos = i; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(j < m) add(id(i, j), id(i, j + 1), 1); if(j > 1) add(id(i, j), id(i, j - 1), 1); if(i + c[j] <= n && i + c[j] >= 1) add(id(i, j), id(i + c[j], j), abs(c[j] * 2)); } } for(int i = 1; i <= m; i++) add(id(n, i), n * m + 1, 0); dij(id(1, pos)); if(dis[n * m + 1] > INF) puts("-1"); else printf("%d ", dis[n * m + 1]); return 0; }