Submission #87863

#	Time	Username	Problem	Language	Result	Execution time	Memory
87863		KCSC	Soccer (JOI17_soccer)	C++14	100 / 100	642 ms	23584 KiB

soccer

#include <bits/stdc++.h>
using namespace std;

const int DIM = 505;

const int dx[5] = {0, -1, 0, 1, 0};
const int dy[5] = {0, 0, 1, 0, -1};

long long dp[DIM][DIM][5], dst[DIM][DIM];

pair<int, int> pos[DIM * DIM];

deque<pair<int, int>> que;

priority_queue<pair<long long, tuple<int, int, int>>, 
			   vector<pair<long long, tuple<int, int, int>>>,
			   greater<pair<long long, tuple<int, int, int>>>> prq;

int main(void) {
#ifdef HOME
	freopen("soccer.in", "r", stdin);	
	freopen("soccer.out", "w", stdout);
#endif
	int n, m, a, b, c, k; 
	cin >> n >> m >> a >> b >> c >> k;
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= m; ++j) {
			dst[i][j] = 1LL << 60;
			for (int k = 0; k <= 4; ++k) {
				dp[i][j][k] = 1LL << 60; } } }
	for (int i = 1; i <= k; ++i) {	
		int x, y; cin >> x >> y; dst[x][y] = 0; 
		pos[i] = make_pair(x, y); }
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= m; ++j) {
			if (dst[i][j] == 0) {
				que.push_back(make_pair(i, j)); } } }
	while (que.size()) {
		int x, y; tie(x, y) = que.front(); que.pop_front();
		for (int d = 1; d <= 4; ++d) {
			int xx = x + dx[d], yy = y + dy[d];
			if (xx >= 0 and xx <= n and yy >= 0 and yy <= m and dst[xx][yy] == 1LL << 60) {
				dst[xx][yy] = dst[x][y] + c; que.push_back(make_pair(xx, yy)); } } }
	dp[pos[1].first][pos[1].second][0] = 0; 
	prq.push(make_pair(0, make_tuple(pos[1].first, pos[1].second, 0)));
	while (prq.size()) {
		long long ds; int x, y, z;
		ds = prq.top().first; tie(x, y, z) = prq.top().second; prq.pop();
		if (dp[x][y][z] != ds) {
			continue; }
		if (z == 0) {
			for (int d = 1; d <= 4; ++d) {
				if (dp[x][y][d] > dp[x][y][0] + b) {
					dp[x][y][d] = dp[x][y][0] + b; prq.push(make_pair(dp[x][y][d], make_tuple(x, y, d))); }
				int xx = x + dx[d], yy = y + dy[d];
				if (xx >= 0 and xx <= n and yy >= 0 and yy <= m and dp[xx][yy][0] > dp[x][y][0] + c) {
					dp[xx][yy][0] = dp[x][y][0] + c; prq.push(make_pair(dp[xx][yy][0], make_tuple(xx, yy, 0))); } } }
		else {
			if (dp[x][y][0] > dp[x][y][z] + dst[x][y]) {
				dp[x][y][0] = dp[x][y][z] + dst[x][y]; prq.push(make_pair(dp[x][y][0], make_tuple(x, y, 0))); }
			int xx = x + dx[z], yy = y + dy[z];
			if (xx >= 0 and xx <= n and yy >= 0 and yy <= m and dp[xx][yy][z] > dp[x][y][z] + a) {
				dp[xx][yy][z] = dp[x][y][z] + a; prq.push(make_pair(dp[xx][yy][z], make_tuple(xx, yy, z))); } } }
	cout << dp[pos[k].first][pos[k].second][0] << endl;
	return 0; }	

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