自动搬运

查看原文

来自洛谷，原作者为

	Vae_L 海纳百川，有容乃大，无欲则刚

搬运于2025-08-24 23:02:48，当前版本为作者最后更新于2025-08-18 21:04:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这不就是板子。

根本不用显性建边，把当前的层数和手柄所在的位置存下来，之后枚举 $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;
}