Submission #670480

#	Time	Username	Problem	Language	Result	Execution time	Memory
670480		Sohsoh84	Soccer (JOI17_soccer)	C++17	35 / 100	750 ms	262144 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 = 500 + 10;

ll n, m, A, B, C, k, p_dist[MAXN][MAXN], SX, SY, TX, TY, dist[MAXN][MAXN][2];
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;
		}

		add(x, y, 0, d);	
		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);
	
		for (int i = 0; i <= n; i++)
			add(i, y, 0, d + A * abs(x - i) + B);	
		for (int i = 0; i <= m; i++)
			add(x, i, 0, d + A * abs(y - i) + B);
	}


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

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