Submission #32813

#	Time	Username	Problem	Language	Result	Execution time	Memory
32813		aome	Soccer (JOI17_soccer)	C++14	100 / 100	843 ms	28148 KiB

soccer

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

#define int long long

typedef pair<int, int> ii;
typedef pair<ii, ii> p;
const int N = 505;
const int INF = 1e18;

int h, w;
int n, A, B, C;
int endX, endY;
int res = INF;
int g[N][N];
int f[N][N][5]; 
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
priority_queue<p> pq;

signed main() {
	ios::sync_with_stdio(false);
	cin >> h >> w;
	cin >> A >> B >> C;
	cin >> n;
	for (int i = 0; i <= h; ++i) {
		for (int j = 0; j <= w; ++j) {
			for (int k = 0; k < 5; ++k) {
				f[i][j][k] = INF;
			}
		}
	}
	memset(g, -1, sizeof g);
	queue<ii> qu;
	for (int i = 0; i < n; ++i) {
		int x, y; cin >> x >> y;
		if (!i) {
			f[x][y][4] = 0, pq.push(p(ii(0, 4), ii(x, y)));
		}
		if (i == n - 1) {
			endX = x, endY = y;
		}
		g[x][y] = 0, qu.push(ii(x, y));
	}
	while (qu.size()) {
		int x = qu.front().fi, y = qu.front().se; qu.pop();
		for (int i = 0; i < 4; ++i) {
			int nx = x + dx[i], ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx > h || ny > w) continue;
			if (g[nx][ny] == -1) {
				g[nx][ny] = g[x][y] + 1, qu.push(ii(nx, ny));
			}
		}
	}
	while (pq.size()) {
		int x = pq.top().se.fi, y = pq.top().se.se, F = -pq.top().fi.fi, t = pq.top().fi.se; pq.pop();
		if (F != f[x][y][t]) continue;
		res = min(res, F + (abs(x - endX) + abs(y - endY)) * C);
		if (t != 4 && f[x][y][4] > f[x][y][t] + g[x][y] * C) {
			f[x][y][4] = f[x][y][t] + g[x][y] * C, pq.push(p(ii(-f[x][y][4], 4), ii(x, y)));
		}
		if (t != 4) {
			int nx = x + dx[t], ny = y + dy[t];
			if (nx < 0 || ny < 0 || nx > h || ny > w) {}
			else if (f[nx][ny][t] > f[x][y][t] + A) {
				f[nx][ny][t] = f[x][y][t] + A, pq.push(p(ii(-f[nx][ny][t], t), ii(nx, ny)));
			}
		}
		if (t == 4) {
			for (int i = 0; i < 4; ++i) {
				int nx = x + dx[i], ny = y + dy[i];
				if (nx < 0 || ny < 0 || nx > h || ny > w) continue;
				if (f[nx][ny][4] > f[x][y][4] + C) {
					f[nx][ny][4] = f[x][y][4] + C, pq.push(p(ii(-f[nx][ny][4], 4), ii(nx, ny)));
				}
				if (f[nx][ny][i] > f[x][y][4] + A + B) {
					f[nx][ny][i] = f[x][y][4] + A + B, pq.push(p(ii(-f[nx][ny][i], i), ii(nx, ny)));
				}
			}
		}
	}
	cout << res << '\n';
	// int x, y, t;
	// while (cin >> x >> y >> t) cout << f[x][y][t] << '\n';
}

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