답안 #33343 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
33343	2017-10-24T07:56:51 Z	ngkan146	Soccer (JOI17_soccer)	C++	100 / 100	559 ms	19572 KB

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.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	79 ms	14964 KB	Output is correct
2	Correct	0 ms	13388 KB	Output is correct
3	Correct	329 ms	19572 KB	Output is correct
4	Correct	359 ms	19572 KB	Output is correct
5	Correct	83 ms	13548 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	419 ms	19572 KB	Output is correct
2	Correct	366 ms	19572 KB	Output is correct
3	Correct	279 ms	19572 KB	Output is correct
4	Correct	276 ms	19572 KB	Output is correct
5	Correct	296 ms	19572 KB	Output is correct
6	Correct	359 ms	19572 KB	Output is correct
7	Correct	386 ms	19572 KB	Output is correct
8	Correct	346 ms	19572 KB	Output is correct
9	Correct	379 ms	19572 KB	Output is correct
10	Correct	53 ms	14964 KB	Output is correct
11	Correct	386 ms	19572 KB	Output is correct
12	Correct	336 ms	19572 KB	Output is correct
13	Correct	219 ms	19572 KB	Output is correct
14	Correct	329 ms	19572 KB	Output is correct
15	Correct	283 ms	19572 KB	Output is correct

Subtask #3
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	79 ms	14964 KB	Output is correct
2	Correct	0 ms	13388 KB	Output is correct
3	Correct	329 ms	19572 KB	Output is correct
4	Correct	359 ms	19572 KB	Output is correct
5	Correct	83 ms	13548 KB	Output is correct
6	Correct	419 ms	19572 KB	Output is correct
7	Correct	366 ms	19572 KB	Output is correct
8	Correct	279 ms	19572 KB	Output is correct
9	Correct	276 ms	19572 KB	Output is correct
10	Correct	296 ms	19572 KB	Output is correct
11	Correct	359 ms	19572 KB	Output is correct
12	Correct	386 ms	19572 KB	Output is correct
13	Correct	346 ms	19572 KB	Output is correct
14	Correct	379 ms	19572 KB	Output is correct
15	Correct	53 ms	14964 KB	Output is correct
16	Correct	386 ms	19572 KB	Output is correct
17	Correct	336 ms	19572 KB	Output is correct
18	Correct	219 ms	19572 KB	Output is correct
19	Correct	329 ms	19572 KB	Output is correct
20	Correct	283 ms	19572 KB	Output is correct
21	Correct	89 ms	14196 KB	Output is correct
22	Correct	446 ms	19572 KB	Output is correct
23	Correct	459 ms	16500 KB	Output is correct
24	Correct	533 ms	16500 KB	Output is correct
25	Correct	416 ms	19572 KB	Output is correct
26	Correct	499 ms	19572 KB	Output is correct
27	Correct	233 ms	13932 KB	Output is correct
28	Correct	303 ms	13920 KB	Output is correct
29	Correct	449 ms	16500 KB	Output is correct
30	Correct	266 ms	13656 KB	Output is correct
31	Correct	476 ms	19572 KB	Output is correct
32	Correct	553 ms	19572 KB	Output is correct
33	Correct	363 ms	19572 KB	Output is correct
34	Correct	559 ms	19572 KB	Output is correct
35	Correct	246 ms	13552 KB	Output is correct

답안 #33343

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 30.0 / 30.0

Subtask #3 65.0 / 65.0

Subtask #1
5.0 / 5.0

Subtask #2
30.0 / 30.0

Subtask #3
65.0 / 65.0