题解：P10948 升降梯上

· · 题解

这不就是板子。

根本不用显性建边，把当前的层数和手柄所在的位置存下来，之后枚举 C_{i}，直接求代价，跑一遍最短路即可。

时间复杂度：O(m \log m)。

哦当然，这指的是 dijkstra 算法的理论复杂度（当然它很稳定），其中的 m 代表边数。

每个点都有 m 条向外的边，所以边数是 n \times m 的，当然很多端点会比 1 小或比 n 大，不合法直接判掉。



#include<bits/stdc++.h> 
using namespace std;
int d[500005],n,m,s,head[500005],cnt,vis[500005],c[500005];
struct node{
    int to,next,w;
}a[500005];
struct edge{
    int w,to,pos;
    bool operator <(const edge &x)const
    {
        return x.w<w;
    }
};
priority_queue<edge>q;
void dijkstra()
{
    memset(d,0x3f,sizeof d);
    d[1]=0;
    memset(vis,0,sizeof vis);
    while(!q.empty())
    {
        int x=q.top().to;
        int z=q.top().pos;
        q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=1;i<=m;i++)
        {
            int v=x+c[i];
            if(v<1||v>n) continue;
            int w=2*abs(c[i])+abs(z-i);
            if(d[v]>d[x]+w)
            {
                d[v]=d[x]+w;
                if(!vis[v]) q.push({d[v],v,i});
            }
        } 
    }
}
int main()
{ 
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>c[i];
        if(!c[i]) q.push({0,1,i});
    }
    dijkstra();
    cout<<(d[n]>=0x3f3f3f3f?-1:d[n]);
    return 0;
}