Submission #590122

#	Time	Username	Problem	Language	Result	Execution time	Memory
590122		dutinmeow	Soccer (JOI17_soccer)	C++17	100 / 100	620 ms	117120 KiB

soccer

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e15;
const array<int, 4> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};

int main() {
	int N, M, Q;
	long long A, B, C;
	cin >> N >> M >> A >> B >> C >> Q;
	N++, M++;

	vector<int> X(Q), Y(Q);
	queue<pair<int, int>> que;
	vector<vector<long long>> bfs(N, vector<long long>(M, INF));
	for (int i = 0; i < Q; i++) {
		int x, y;
		cin >> x >> y;
		que.emplace(x, y);
		bfs[x][y] = 0;
		X[i] = x, Y[i] = y;
	}
	while (!que.empty()) {
		auto [x, y] = que.front(); que.pop();
		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k], ny = y + dy[k];
			if (0 <= nx && nx < N && 0 <= ny && ny < M && bfs[nx][ny] == INF) {
				bfs[nx][ny] = bfs[x][y] + 1;
				que.emplace(nx, ny);
			}
		}
	}

	int n = 0;
	vector<vector<int>> nM(N, vector<int>(M)), nX(N, vector<int>(M)), nY(N, vector<int>(M));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			nM[i][j] = n++;
			nX[i][j] = n++;
			nY[i][j] = n++;
		}
	}

	vector<vector<pair<int, long long>>> G(n);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			G[nM[i][j]].emplace_back(nX[i][j], B);
			G[nM[i][j]].emplace_back(nY[i][j], B);
			G[nX[i][j]].emplace_back(nM[i][j], C * bfs[i][j]);
			G[nY[i][j]].emplace_back(nM[i][j], C * bfs[i][j]);
		}
	}
	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < M; j++) {
			G[nM[i][j]].emplace_back(nM[i + 1][j], C);
			G[nM[i + 1][j]].emplace_back(nM[i][j], C);
			G[nX[i][j]].emplace_back(nX[i + 1][j], A);
			G[nX[i + 1][j]].emplace_back(nX[i][j], A);
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M - 1; j++) {
			G[nM[i][j]].emplace_back(nM[i][j + 1], C);
			G[nM[i][j + 1]].emplace_back(nM[i][j], C);
			G[nY[i][j]].emplace_back(nY[i][j + 1], A);
			G[nY[i][j + 1]].emplace_back(nY[i][j], A);
		}
	}

	using pq_node = pair<long long, int>;
	priority_queue<pq_node, vector<pq_node>, greater<pq_node>> pq;
	vector<long long> dis(n, INF);

	pq.emplace(0, nM[X[0]][Y[0]]);
	dis[nM[X[0]][Y[0]]] = 0;
	while (!pq.empty()) {
		auto [d, u] = pq.top(); pq.pop();
		for (auto [v, w] : G[u]) {
			if (d + w < dis[v]) {
				dis[v] = d + w;
				pq.emplace(dis[v], v);
			}
		}
	}

	cout << min({dis[nM[X[Q - 1]][Y[Q - 1]]], dis[nX[X[Q - 1]][Y[Q - 1]]], dis[nY[X[Q - 1]][Y[Q - 1]]]}) << '\n';
}

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