题解：P5100 [JOI 2017 Final] 足球 / Soccer

很好的题！

考虑球只有两种状态，在空中（被人踢着），或者在地上（被人带着），所以考虑拆点。

在地上你可以向四个方向自由移动（花费

C

的代价），也可以进入某种飞行状态（花费

B

的代价），然后每次都花费 $A$ 的代价向一个固定方向走。

一旦球落地了，那么必须要有一个人来接应这个球。所以再加上

C \times K

，

K

是离落地这个点最近的球员的距离。

这样为啥是对的？因为如果有人踢过球再去控球的话，不如直接把球运过去来的痛快。

所以可以拆出来

5 \times H \times W

个点，分别表示在地上，向东/西/南/北飞的状态，然后跑单源最短路就行了。

时间复杂度

\Theta(HW \log HW)

，常数略大。

CPP

#include <bits/stdc++.h>
#define int long long
#define FAST ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
/*
by qqqaaazzz
*/
int n,m;
int A,B,C;
int q;
pair<int,int> p[100010];
int dis[510][510];
int fx[] = {0,0,-1,1};
int fy[] = {-1,1,0,0};
vector<pair<int,int> > v[2000010];

int t(int x,int y,int id){
	return id*(n+1)*(m+1)+x*(m+1)+y;
}
bool vis[2000010];
int D[2000010];

void Dijkstra(int st){
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
	q.push(make_pair(0,st));
	memset(D,0x3f,sizeof(D));
	memset(vis,0,sizeof(vis));
	D[st] = 0;
	while(!q.empty()){
		pair<int,int> p = q.top();
		q.pop();
		if(vis[p.second]) continue;
		vis[p.second] = true;
		for (auto i : v[p.second]){
			if(p.first+i.second<D[i.first]){
				D[i.first] = p.first+i.second;
				q.push(make_pair(D[i.first],i.first));
			}
		}
	}
	return;
}

signed main()
{
	cin >> n >> m;
	cin >> A >> B >> C;
	cin >> q;
	for (int i=1;i<=q;i++){
		cin >> p[i].first >> p[i].second;
	}
	//求出来每个点最近的球员
	memset(dis,0x3f,sizeof(dis));
	queue<pair<int,int> > Q;
	for (int i=1;i<=q;i++){
		dis[p[i].first][p[i].second] = 0;
		Q.push(p[i]);
	}
	while(!Q.empty()){
		pair<int,int> f = Q.front();
		Q.pop();
		for (int i=0;i<4;i++){
			int dx = f.first+fx[i];
			int dy = f.second+fy[i];
			if(dx>=0&&dx<=n&&dy>=0&&dy<=m&&dis[f.first][f.second]+1<dis[dx][dy]){
				dis[dx][dy] = dis[f.first][f.second]+1;
				Q.push({dx,dy});
			}
		}
	}
	
	for (int i=0;i<=n;i++){
		for (int j=0;j<=m;j++){
			for (int f=1;f<=4;f++){
				int dx = i+fx[f-1],dy = j+fy[f-1];
				if(dx>=0&&dx<=n&&dy>=0&&dy<=m){
					v[t(i,j,0)].push_back({t(dx,dy,0),C});
					v[t(i,j,f)].push_back({t(dx,dy,f),A});
				}
				v[t(i,j,0)].push_back({t(i,j,f),B});
				v[t(i,j,f)].push_back({t(i,j,0),dis[i][j]*C});
			}
		}
	}
	Dijkstra(t(p[1].first,p[1].second,0));
	cout << D[t(p[q].first,p[q].second,0)] << "\n";
	return 0;
}

题解：P5100 [JOI 2017 Final] 足球 / Soccer

文章操作

相关推荐

评论

题解：P5100 [JOI 2017 Final] 足球 / Soccer