自动搬运

查看原文

来自洛谷，原作者为

	Rachel_in **

搬运于2025-08-24 21:51:19，当前版本为作者最后更新于2019-02-26 10:53:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

没看见有SPFA的题解，那我就来一发吧！

我们对于每一个位置，将他们与自己走三步的点进行连边，边的权值为$t*3+$到达的点的权值。如图所示（注意它可以向上再向下再向上这类的情况，所以有16个方向）：

随后，从起点$(1,1)$跑一遍SPFA，最后统计答案分别从$(n,n),(n-1,n),(n,n-1),(n-2,n),(n,n-2),(n-1,n-1)$中转移过来。具体看代码。

由于本题边的构造可以发现很难卡SPFA，SPFA没有死，而且就算卡了复杂度也可以接受QWQ

#include<bits/stdc++.h>
#include<queue>
using namespace std;
const int N=105;
inline int read(){//快读
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int cnt,fir[N*N],nxt[N*N*16],go[N*N*16],val[N*N*16];//邻接表存边
int n,t,a[N][N];
long long ans,d[N*N];
bool vis[N*N];
int h(int x,int y)//给每个点设立一个编号
{
	return (x-1)*n+y;	
}
inline void Add(int u,int v,int w)
{
	nxt[++cnt]=fir[u];	
	fir[u]=cnt;
	go[cnt]=v;
	val[cnt]=w;
}//连边
const int dx[16]={-2,-1,1,2,2,1,-1,-2,0,1,0,-1,0,3,0,-3};
const int dy[16]={1,2,2,1,-1,-2,-2,-1,1,0,-1,0,3,0,-3,0};//枚举16个方向

inline void COCO_made_me_Do_it(int x,int y)
{
	for(int i=0;i<16;i++)
	{
		int xx=x+dx[i],yy=y+dy[i];	
		if(xx>0&&xx<=n&&yy>0&&yy<=n)//判断是否越界
		{
			Add(h(x,y),h(xx,yy),a[xx][yy]+3*t);//建边；
		}	
	}
}
queue<int> q;
void SPFA(int x,int y)//SPFA跑最短路
{
	memset(vis,false,sizeof(vis));
	memset(d,0x3f,sizeof(d));
	d[h(x,y)]=0;
	vis[h(x,y)]=true;
	q.push(h(x,y));
	while(!q.empty())
	{
		int xx=q.front();q.pop();
		vis[xx]=false;
		for(int e=fir[xx];e;e=nxt[e])
		{
			int yy=go[e];
			if(d[xx]+val[e]<d[yy])
			{
				d[yy]=d[xx]+val[e];	
				if(!vis[yy])
				{
					vis[yy]=true;q.push(yy);
				}
			}
		}	
	}
}
int main()
{
	n=read();t=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			a[i][j]=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			COCO_made_me_Do_it(i,j);
	SPFA(1,1);
	ans=0x7fffffff;
	ans=min(ans,d[h(n,n)]);
	if(n>=2)ans=min(ans,d[h(n,n-1)]+t);
	if(n>=2)ans=min(ans,d[h(n-1,n)]+t);
	if(n>=3)ans=min(ans,d[h(n-2,n)]+2*t);
	if(n>=3)ans=min(ans,d[h(n,n-2)]+2*t);
	if(n>=2)ans=min(ans,d[h(n-1,n-1)]+2*t);//没什么意义的特判，更新答案
	printf("%lld\n",ans);
	return 0;
}