Submission #684251

#	Time	Username	Problem	Language	Result	Execution time	Memory
684251		ethening	Soccer (JOI17_soccer)	C++17	0 / 100	973 ms	262144 KiB

soccer

#include "bits/stdc++.h"
#include <climits>
#include <queue>
#include <utility>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

struct edge {
	int to;
	ll weight;
};

pii pos[100005];
int close[505][505];
int dex[505][505][5];
vector<edge> E[1255010];
ll ans[1255010];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int h, w;
	cin >> h >> w;
	int A, B, C;
	cin >> A >> B >> C;
	int n;
	cin >> n;
	memset(close, -1, sizeof(close));
	
	queue<pii> Q;
	for (int i = 0; i < n; i++) {
		cin >> pos[i].first >> pos[i].second;
		close[pos[i].first][pos[i].second] = 0;
		Q.push(pos[i]);
	}

	while (!Q.empty()) {
		auto [x, y] = Q.front();
		Q.pop();
		if (x > 0 && close[x - 1][y] == -1) {
			close[x - 1][y] = close[x][y] + 1;
			Q.push(make_pair(x - 1, y));
 		}
		if (x < h && close[x + 1][y] == -1) {
			close[x + 1][y] = close[x][y] + 1;
			Q.push(make_pair(x + 1, y));
 		}
		if (y > 0 && close[x][y - 1] == -1) {
			close[x][y - 1] = close[x][y] + 1;
			Q.push(make_pair(x, y - 1));
 		}
		if (y < w && close[x][y + 1] == -1) {
			close[x][y + 1] = close[x][y] + 1;
			Q.push(make_pair(x, y + 1));
 		}
	}
	
	int cnt = 0;
	for (int i = 0; i <= h; i++) {
		for (int j = 0; j <= w; j++) {
			for (int k = 0; k < 5; k++) {
				dex[i][j][k] = ++cnt;
			}
		}
	}

	for (int i = 0; i <= h; i++) {
		for (int j = 0; j <= w; j++) {
			E[dex[i][j][0]].push_back({.to = dex[i][j][1], .weight = B});
			E[dex[i][j][0]].push_back({.to = dex[i][j][2], .weight = B});
			E[dex[i][j][0]].push_back({.to = dex[i][j][3], .weight = B});
			E[dex[i][j][0]].push_back({.to = dex[i][j][4], .weight = B});
			
			E[dex[i][j][1]].push_back({.to = dex[i][j][0], .weight = close[i][j] * C});
			E[dex[i][j][2]].push_back({.to = dex[i][j][0], .weight = close[i][j] * C});
			E[dex[i][j][3]].push_back({.to = dex[i][j][0], .weight = close[i][j] * C});
			E[dex[i][j][4]].push_back({.to = dex[i][j][0], .weight = close[i][j] * C});
			if (i > 0) {
				E[dex[i][j][0]].push_back({.to = dex[i - 1][j][0], .weight = C});
				E[dex[i][j][1]].push_back({.to = dex[i - 1][j][1], .weight = A});
			}
			if (i < h) {
				E[dex[i][j][0]].push_back({.to = dex[i + 1][j][0], .weight = C});
				E[dex[i][j][2]].push_back({.to = dex[i + 1][j][2], .weight = A});
			}
			if (j > 0) {
				E[dex[i][j][0]].push_back({.to = dex[i][j - 1][0], .weight = C});
				E[dex[i][j][3]].push_back({.to = dex[i][j - 1][3], .weight = A});
			}
			if (j < w) {
				E[dex[i][j][0]].push_back({.to = dex[i][j + 1][0], .weight = C});
				E[dex[i][j][4]].push_back({.to = dex[i][j + 1][4], .weight = A});
			}
		}
	}

	// for (int i = 1; i <= cnt; i++) {
	// 	cout << "!" << (i - 1) / 5 + 1 << " " << (i - 1) % 5 << endl;
	// 	for (auto [to, weight] : E[i]) {
	// 		cout << (to - 1) / 5 + 1 << " " << (to - 1) % 5 << " " << weight << endl;
	// 	}
	// }

	for (int i = 1; i <= cnt; i++) ans[i] = (ll)1e18;

	int st = dex[pos[0].first][pos[0].second][0];
	int ed = dex[pos[n - 1].first][pos[n - 1].second][0];

	priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> PQ;
	ans[st] = 0;
	PQ.push(make_pair(0, st));
	while (!PQ.empty()) {
		auto [dist, cur] = PQ.top();
		PQ.pop();
		if (ans[cur] < dist) continue;
		if (cur == ed) break;
		for (auto [to, weight] : E[cur]) {
			if (ans[cur] + weight < ans[to]) {
				ans[to] = ans[cur] + weight;
				PQ.push(make_pair(ans[to], to));
			}
		}
	}

	// for (int i = 1; i <= cnt; i++) {
	// 	cout << "#" << (i - 1) / 5 + 1 << " " << (i - 1) % 5 << " " << ans[i] << endl;
	// }
	cout << ans[ed] << endl;
}

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