自动搬运

查看原文

来自洛谷，原作者为

	¶凉笙 Inner Peace

搬运于2025-08-24 22:07:08，当前版本为作者最后更新于2021-09-04 15:05:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

[题解] 「JOI 2017 Final」足球

只用拆三个点！！

不一定更好的阅读体验

不知道为什么题解都是拆成 $6$ 个点的，所谓的“蝴蝶效应”？

而且，一个人最多控几次球根本就不用关心。

首先并不好 DP，传递问题想到建图。

建一层图肯定是不行的，因为有控球和不控球的状态差别，或者说有球滚动和人移动的不同代价，所以需要拆点或者说建分层图（个人感觉本质上是一样的）。

因为人的移动本质上是一样的，所以人带着球的移动可以当成一层来看。

球滚动的过程也需要考虑，因为代价不同（也就是踢球的代价）。

注意：球滚动的过程需要分为两层，横着滚动和竖着滚动，因为这两个方向是不相通的！

如何从滚动过程跳跃到运球过程

如果状态的第一层定义的是人运球的过程，而不是人移动的过程的话，那么从滚动过程的当前点 $(x,y)$ 跳到运球过程的当前点一定需要人来接，这个人一定是离 $(x,y)$ 最近的那个球员，所以如果当前点一定要跳状态到运球状态，需要强制让最近的球员瞬时过来接。

小结

我觉的一大部分人的思路在独立思考的情况下应该是这样拆成三个点来进行最短路的，因为人的一般性思维大部分时间是基于增量法的。

何况上下左右真的没必要，拆成三个点思维难度并没有增加。反而降低了（？

要有建图的意识！

目前 Luogu 全站第二，欢迎hack

坑点

坐标是从 $0$ 开始的，一张图有 $(n+1)\times (m+1)$ 个点而不是 $n\times m$ 个。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template <typename T>
inline T read(){
	T x=0;char ch=getchar();bool fl=false;
	while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+(ch^48);ch=getchar();
	}
	return fl?-x:x;
}
#include <queue>
const int maxn = 1e5 + 10;
const int maxm = 505;
#define LL long long
LL A,B,C;
int n,m,k,X[maxn],Y[maxn];
bool vis[maxm][maxm];
int head[maxm*maxm*3],cnt=0;
struct edge{
	int to,nxt;LL w;
}e[maxm*maxm*30];
inline void link(int u,int v,LL w){
	e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;e[cnt].w=w;
}
LL dis[maxm*maxm*3];
inline int id(int x,int y){
	return x*(m+1)+y;
}
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
#define read() read<int>()
#define Pair pair<LL,int>
#define mp make_pair
bool visit[maxm*maxm*3];
void dij(int s){
	memset(dis,0x3f,sizeof dis);
	priority_queue<Pair,vector<Pair>,greater<Pair> > q;q.push(mp(0,s));
	dis[s]=0;
	while(q.size()){
		int u=q.top().second;q.pop();
		if(visit[u])continue;
		visit[u]=true;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(dis[v]>dis[u]+e[i].w && !visit[v]){
				dis[v]=dis[u]+e[i].w;
				q.push(mp(dis[v],v));
			}
		}
	}
}
LL dist[maxm][maxm];
void bfs(){
	queue<Pair> q;
	for(int i=1;i<=k;i++)q.push(mp(X[i],Y[i])),dist[X[i]][Y[i]]=0;
	while(q.size()){
		int x=q.front().first,y=q.front().second;q.pop();
		for(int i=0;i<4;i++){
			int xx=x+dx[i],yy=y+dy[i];
			if(xx<0 || xx>n || yy<0 || yy>m)continue;
			if(vis[xx][yy] || dist[xx][yy])continue;
			dist[xx][yy]=dist[x][y]+1;
			q.push(mp(xx,yy));
		}
	}
}
int main(){
	n=read();m=read();
	A=read<LL>();B=read<LL>();C=read<LL>();
	k=read();
	for(int i=1;i<=k;i++)X[i]=read(),Y[i]=read(),vis[X[i]][Y[i]]=true;
	bfs();
	for(int x=0;x<=n;x++){
		for(int y=0;y<=m;y++){
			for(int i=0;i<4;i++){
				int xx=x+dx[i],yy=y+dy[i];
				if(xx<0 || xx>n || yy<0 || yy>m)continue;
				link(id(x,y),id(xx,yy),C);
			}
			link(id(x,y),id(x,y)+(n+1)*(m+1),B);
			link(id(x,y),id(x,y)+2*(n+1)*(m+1),B);
		}
	}
	for(int x=0;x<=n;x++){
		for(int y=0;y<=m;y++){
			for(int i=0;i<2;i++){
				int xx=x+dx[i],yy=y+dy[i];
				if(xx<0 || xx>n || yy<0 || yy>m)continue;
				link(id(x,y)+(n+1)*(m+1),id(xx,yy)+(n+1)*(m+1),A);
			}
			link(id(x,y)+(n+1)*(m+1),id(x,y),dist[x][y]*C);
		}
	}
	for(int x=0;x<=n;x++){
		for(int y=0;y<=m;y++){
			for(int i=2;i<4;i++){
				int xx=x+dx[i],yy=y+dy[i];
				if(xx<0 || xx>n || yy<0 || yy>m)continue;
				link(id(x,y)+2*(n+1)*(m+1),id(xx,yy)+2*(n+1)*(m+1),A);
			}
			link(id(x,y)+2*(n+1)*(m+1),id(x,y),dist[x][y]*C);
		}
	}
	dij(id(X[1],Y[1]));
	printf("%lld\n",dis[id(X[k],Y[k])]);
	return 0;
}