Submission #33343

#	Time	Username	Problem	Language	Result	Execution time	Memory
33343		ngkan146	Soccer (JOI17_soccer)	C++98	100 / 100	559 ms	19572 KiB

soccer

#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<ll,int> ii;
#define fi first
#define se second
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
ll A,B,C;
int n,h,w;
ll dp0[505][505], dp1[505][505][4];
bool player[505][505];
int min_distance[505][505];
void prep(){
	queue <int> q;
	for(int i=0;i<=h;i++)
		for(int j=0;j<=w;j++){
			if (player[i][j]) min_distance[i][j] = 0, q.push(i * 501 + j);
			else min_distance[i][j] = 100000;
		}
	while(q.size()){
		int x = q.front() / 501;
		int y = q.front() % 501;
		q.pop();
		for(int k=0;k<4;k++){
			int X = x + dx[k];
			int Y = y + dy[k];
			if (0 > X || X > h || 0 > Y || Y > w) continue;
			if (min_distance[X][Y] > min_distance[x][y] + 1)
				min_distance[X][Y] = min_distance[x][y] + 1,
				q.push(X * 501 + Y);
		}
	}
}
#define x1 asd
#define y1 jnda
#define xn addaf
#define yn nln
int x1,y1,xn,yn;
void prep_dp(){
	for(int i=0;i<=h;i++)
		for(int j=0;j<=w;j++)
			dp0[i][j] = dp1[i][j][0] = dp1[i][j][1] = dp1[i][j][2] = dp1[i][j][3] = (ll) 1e18;
	dp0[x1][y1] = 0;
}
bool  markh[505], markw[505];

void cal_dp(){
	priority_queue <ii,vector<ii>,greater<ii> > pq;
	
	pq.push(ii(0, x1 * 3500 + y1 * 5));
		
	while(pq.size()){
		int x = pq.top().se / 3500;
		int y = (pq.top().se % 3500) / 5;
		int type = pq.top().se % 5;
		ll dis = pq.top().fi;
		pq.pop();
		
		if (type == 0 && dp0[x][y] != dis) continue;
		if (type && dp1[x][y][type-1] != dis) continue;
		
		if (type == 0){
			for(int k=0;k<4;k++){
				int X = x + dx[k];
				int Y = y + dy[k];
				if (0 > X || X > h || 0 > Y || Y > w) continue;
				if (dp1[X][Y][k] > dp0[x][y] + A + B)
					dp1[X][Y][k] = dp0[x][y] + A + B,
					pq.push(ii(dp1[X][Y][k], X * 3500 + Y * 5 + k+1));
					
				if (dp0[X][Y] > dp0[x][y] + C)
					dp0[X][Y] = dp0[x][y] + C,
					pq.push(ii(dp0[X][Y], X * 3500 + Y * 5 + 0));
			}
		}
		else{
			int X = x + dx[type-1];
			int Y = y + dy[type-1];
			if (dp1[x][y][type-1] + min_distance[x][y] * C < dp0[x][y])
				dp0[x][y] = dp1[x][y][type-1] + min_distance[x][y] * C,
				pq.push(ii(dp0[x][y], x*3500 + y*5));
			if (0 > X || X > h || 0 > Y || Y > w) continue;
			if (dp1[X][Y][type-1] > dp1[x][y][type-1] + A)
				dp1[X][Y][type-1] = dp1[x][y][type-1] + A,
				pq.push(ii(dp1[X][Y][type-1], X * 3500 + Y * 5 + type));
			
		}
	}
}
int main(){
	iostream::sync_with_stdio(0);
	cin >> h >> w;
	cin >> A >> B >> C;
	cin >> n;
	for(int i=1;i<=n;i++){
		int x,y;
		cin >> x >> y; 
		if (i == 1) x1 = x, y1 = y;
		if (i == n) xn = x, yn = y;
		player[x][y] = 1;
	}
	prep();
	prep_dp();
	cal_dp();
	cout << dp0[xn][yn];
}
/*
500 500 
1 3 6
3
1 1
0 4
6 5
*/

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65