제출 #670482

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
670482		Sohsoh84	Soccer (JOI17_soccer)	C++17	100 / 100	555 ms	231232 KiB

soccer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pair<pll, int>> PX;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 2e3 + 10;

ll n, m, A, B, C, k, p_dist[MAXN][MAXN], SX, SY, TX, TY, dist[MAXN][MAXN][6];
queue<pll> q;
priority_queue<PX, vector<PX>, greater<PX>> pq;

inline void add_p(int x, int y, ll d) {
	if (x < 0 || y < 0 || x > n || y > m || p_dist[x][y] <= d) return;
	p_dist[x][y] = d;
	q.push({x, y});
}

inline void add(int x, int y, int b, ll d) {
	if (x < 0 || y < 0 || x > n || y > m || dist[x][y][b] <= d) return;
	dist[x][y][b] = d;
	pq.push({d, {{x, y}, b}});
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> A >> B >> C >> k;

	memset(p_dist, 63, sizeof p_dist);
	for (int i = 1; i < k; i++) {
		int x, y;
		cin >> x >> y;
		if (i == 1) SX = x, SY = y;
		add_p(x, y, 0);
	}

	cin >> TX >> TY;
	while (!q.empty()) {
		auto [x, y] = q.front();
		q.pop();
		ll d = p_dist[x][y];

		add_p(x - 1, y, d + 1);
		add_p(x + 1, y, d + 1);
		add_p(x, y - 1, d + 1);
		add_p(x, y + 1, d + 1);
	}

	memset(dist, 63, sizeof dist);
	add(SX, SY, 0, 0);

	while (!pq.empty()) {
		ll d = pq.top().X, x = pq.top().Y.X.X, y = pq.top().Y.X.Y, b = pq.top().Y.Y;
		pq.pop();
		if (d != dist[x][y][b]) continue;
	
		if (!b) {
			add(x, y, 1, d + p_dist[x][y] * C);
			continue;
		}

		if (b == 1) {
			add(x, y, 0, d);	
			add(x, y, 2, d + B);	
			add(x, y, 3, d + B);	
			add(x, y, 4, d + B);	
			add(x, y, 5, d + B);	
			add(x + 1, y, 1, d + C);
			add(x - 1, y, 1, d + C);
			add(x, y + 1, 1, d + C);
			add(x, y - 1, 1, d + C);
			continue;
		}

		add(x, y, 0, d);
		if (b == 2) add(x - 1, y, b, d + A);
		if (b == 3) add(x, y - 1, b, d + A);
		if (b == 4) add(x + 1, y, b, d + A);
		if (b == 5) add(x, y + 1, b, d + A);
	}

	cout << dist[TX][TY][0] << endl;
	return 0;
}

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