Submission #33342

#	Time	Username	Problem	Language	Result	Execution time	Memory
33342		ngkan146	Soccer (JOI17_soccer)	C++98	5 / 100	649 ms	21612 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;
}
void cal_dp(){
	for(int _time=0;_time<=1;_time++){
		priority_queue <ii,vector<ii>,greater<ii> > pq;
		for(int i=0;i<=h;i++)
			for(int j=0;j<=w;j++)
				pq.push(ii(dp0[i][j], i*3500 + j * 5 + 0));
		
		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 (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));
			}
			
		}
		
		
		for(int i=0;i<=h;i++)
			for(int j=0;j<=w;j++)
				for(int t=0;t<4;t++)
					dp0[i][j] = min(dp0[i][j], dp1[i][j][t] + min_distance[i][j] * C),
					dp1[i][j][t] = (ll) 1e18;
		/*			
		for(int i=0;i<=h;i++){
			for(int j=0;j<=w;j++){
				if (dp0[i][j] != (ll) 1e18) cout << dp0[i][j] << ' ';
				else cout << -1;
			}
			cout << endl;
		}
		cout << endl;
		*/
	}
}
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: 0 / 30
• Subtask 3: 0 / 65