제출 #1178195

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178195		Tsagana	Soccer (JOI17_soccer)	C++20	35 / 100	305 ms	29192 KiB

soccer

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

const int inf = 1e9 + 7;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

int h, w, n, a, b, c;
int s[100010];
int t[100010];
int P[510][510];
int B[510][510][5];
pq<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> q;
pq<array<int, 4>, vector<array<int, 4>>, greater<array<int, 4>>> Q;

bool inside(int x, int y) {
	return 0 <= x && x <= h && 0 <= y && y <= w;
}

void FILL() {
	for (int i = 0; i <= h; i++)
	for (int j = 0; j <= w; j++) {
		P[i][j] = -1;
	}

	for (int i = 1; i <= n; i++) {
		P[s[i]][t[i]] = 0;
		q.push({s[i], t[i]});
	}

	while (!q.empty()) {
		auto [x, y] = q.top(); q.pop();

		for (int i = 0; i < 4; i++) {
			int X = x + dx[i], Y = y + dy[i];
			if (!inside(X, Y) || P[X][Y] != -1) continue ;
			P[X][Y] = P[x][y] + 1;
			q.push({X, Y}); 
		}
	}
}

void PUSH(int x, int y, int d, int t) {
	if (!inside(x, y) || B[x][y][d] <= t) return ;
	Q.push({B[x][y][d] = t, x, y, d});
}

void CALC() {
	memset(B, 0x3f, sizeof B);
	PUSH(s[1], t[1], 4, 0);
	B[s[1]][t[1]][4] = 0;

	while (!Q.empty()) {
		auto [k, x, y, d] = Q.top(); Q.pop();
		if (B[x][y][d] < k) continue ;
		if (d != 4) {
			PUSH(x + dx[d], y + dy[d], d, k + a);
			PUSH(x, y, 4, k + P[x][y] * c);
			continue ;
		}
		for (int i = 0; i < 4; i++) {
			int X = x + dx[i], Y = y + dy[i];
			PUSH(X, Y, i, k + a + b);
			PUSH(X, Y, 4, k + c);
		}
	}
}

void solve () {
	cin >> h >> w >> a >> b >> c >> n;
	for (int i = 1; i <= n; i++) cin >> s[i] >> t[i];

	FILL();
	CALC();

	cout << B[s[n]][t[n]][4];
}
signed main() {IOS solve(); return 0;}

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