Submission #684341

#	Time	Username	Problem	Language	Result	Execution time	Memory
684341		ethening	Soccer (JOI17_soccer)	C++17	100 / 100	314 ms	89588 KiB

soccer

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

// pii pos[100005];
int close[505][505];
// int dex[505][505][5];
vector<pair<int, ll>> E[753005];
ll ans[753005];

bool vis[753005];

queue<pii> Q;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> PQ;

int dex(int x, int y, int z) {
	return (x * 501 + y) * 3 + z;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int h, w;
	cin >> h >> w;
	ll A, B, C;
	cin >> A >> B >> C;
	int n;
	cin >> n;
	memset(close, -1, sizeof(close));
	
	int st, ed;

	for (int i = 0; i < n; i++) {
		int tmp, tmp2;
		cin >> tmp >> tmp2;
		if (i == 0) {
			st = dex(tmp, tmp2,  0);
		}
		if (i == n - 1) {
			ed = dex(tmp, tmp2, 0);
		}
		close[tmp][tmp2] = 0;
		Q.push(make_pair(tmp, tmp2));
	}

	while (!Q.empty()) {
		pii a = Q.front();
		Q.pop();
		if (a.first > 0 && close[a.first - 1][a.second] == -1) {
			close[a.first - 1][a.second] = close[a.first][a.second] + 1;
			Q.push(make_pair(a.first - 1, a.second));
 		}
		if (a.first < h && close[a.first + 1][a.second] == -1) {
			close[a.first + 1][a.second] = close[a.first][a.second] + 1;
			Q.push(make_pair(a.first + 1, a.second));
 		}
		if (a.second > 0 && close[a.first][a.second - 1] == -1) {
			close[a.first][a.second - 1] = close[a.first][a.second] + 1;
			Q.push(make_pair(a.first, a.second - 1));
 		}
		if (a.second < w && close[a.first][a.second + 1] == -1) {
			close[a.first][a.second + 1] = close[a.first][a.second] + 1;
			Q.push(make_pair(a.first, a.second + 1));
 		}
	}

	for (int i = 0; i <= h; i++) {
		for (int j = 0; j <= w; j++) {
			for (int k = 0; k < 3; k++) {
				ans[dex(i, j, k)] = (ll)1e18;
			}
		}
	}

	for (int i = 0; i <= h; i++) {
		for (int j = 0; j <= w; j++) {
			E[dex(i, j, 0)].reserve(6);
			E[dex(i, j, 1)].reserve(3);
			E[dex(i, j, 2)].reserve(3);
			E[dex(i, j, 0)].push_back(make_pair(dex(i, j, 1), B));
			E[dex(i, j, 0)].push_back(make_pair(dex(i, j, 2), B));
			
			E[dex(i, j, 1)].push_back(make_pair(dex(i, j, 0), close[i][j] * C));
			E[dex(i, j, 2)].push_back(make_pair(dex(i, j, 0), close[i][j] * C));
			if (i > 0) {
				E[dex(i, j, 0)].push_back(make_pair(dex(i - 1, j, 0), C));
				E[dex(i, j, 1)].push_back(make_pair(dex(i - 1, j, 1), A));
			}
			if (i < h) {
				E[dex(i, j, 0)].push_back(make_pair(dex(i + 1, j, 0), C));
				E[dex(i, j, 1)].push_back(make_pair(dex(i + 1, j, 1), A));
			}
			if (j > 0) {
				E[dex(i, j, 0)].push_back(make_pair(dex(i, j - 1, 0), C));
				E[dex(i, j, 2)].push_back(make_pair(dex(i, j - 1, 2), A));
			}
			if (j < w) {
				E[dex(i, j, 0)].push_back(make_pair(dex(i, j + 1, 0), C));
				E[dex(i, j,2)].push_back(make_pair(dex(i, j + 1, 2), 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;
	// 	}
	// }


	ans[st] = 0;
	// cout << st << " " << ed << "!!!" << endl;
	PQ.push(make_pair(0, st));
	while (!PQ.empty()) {
		const pair<ll, int> x = PQ.top();
		PQ.pop();
		if (ans[x.second] < x.first) continue;
		if (x.second == ed) break;
		if (vis[x.second]) continue;
		vis[x.second] = 1;
		for (const pair<int, ll>& y: E[x.second]) {
			if (ans[x.second] + y.second < ans[y.first] && !vis[y.first]) {
				ans[y.first] = ans[x.second] + y.second;
				PQ.push(make_pair(ans[y.first], y.first));
				// cout << x.second << " " << y.first << " " << ans[y.first] << endl;
			}
		}
	}

	cout << ans[ed] << endl;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:131:16: warning: 'ed' may be used uninitialized in this function [-Wmaybe-uninitialized]
  131 |  cout << ans[ed] << endl;
      |                ^

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