最短路之升降梯上

题目

（史上最懒没有之一）

思路

又双叒叕死在最短路了，这题怎么看也像dfs啊，然鹅写挂了，

• 我们把每一层，每一个槽设为图中每一个点，这样好像是一个二维矩阵。
• 既然按照最短路的思路来，首先是建图，建图。。。。。
  这怎么建？？！因为我们平时建图用的都是一维编号，所以我们把，整个二维压到一维中去，这里用一个get函数实现，然后建边，每一层相邻的两个点之间相互建边，彼此到达，既然是相邻，那么时间代价（边权）就是1，然后就是每两层之间建边，

int u=get(i,j),v=get(i+a[j],j);//i表示层数，j表示手柄位置
if(j!=now && (i+a[j])>=1 && (i+a[j])<=n)add(u,v,abs(a[j])*2);

注意两层之间距离为a[j]，而不是1，时间代价为abs(a[j]*2)，

• 为了方便处理，最后可以建一条通向点m*n+1的边，边权为0，
• 数组（尤其实是边）一定要开够！！！！
• 跑一遍最短路即可
  最后附上蒟蒻代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=30010;
const int maxm=1e6+10;
int head[maxn],Next[maxm<<1],ver[maxm<<1],edge[maxm<<1];
int a[maxn];
int tot,now;
int n,m;
void add(int x,int y,int z){
    ver[++tot]=y;
    edge[tot]=z;
    Next[tot]=head[x];
    head[x]=tot;
}
int get(int x,int y){
    return (x-1)*m+y;
}
bool v[maxn];
int d[maxn];
priority_queue<pair<int,int > >q;
void dij(int s){
    memset(d,0x3f,sizeof(d));
    d[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty()){
        int x=q.top().second;
        q.pop();
        if(v[x])continue;
        v[x]=1;
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i],z=edge[i];
            if(d[y]>d[x]+z){
                d[y]=d[x]+z;
                q.push(make_pair(-d[y],y));
            }   
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&a[i]);
        if(a[i]==0)now=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(j<m)add(get(i,j),get(i,j+1),1);
            if(j>1)add(get(i,j),get(i,j-1),1);
            int u=get(i,j),v=get(i+a[j],j);
            if(j!=now && (i+a[j])>=1 && (i+a[j])<=n)add(u,v,abs(a[j])*2);

        }
    }
    for(int i=1;i<=m;i++){
        add(get(n,i),n*m+1,0);
    }
    dij(get(1,now));
    int ans=0x7f7f7f7f;
    if(d[n*m+1]>=1061109567)printf("-1n");
    else printf("%dn",d[n*m+1]);
    return 0;
}