Submission #1180406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180406		jbareja	Soccer (JOI17_soccer)	C++20	100 / 100	792 ms	133192 KiB

soccer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr ll INF = LLONG_MAX;

int H; // wysokość boiska
int W; // szerokość boiska
ll A; // koszt za przelecenie przez kopniętą piłkę 1 metra
ll B; // koszt za kopnięcie piłki
ll C; // koszt za przejście 1 metra
int N; // liczba graczy

vector<pair<int,int>> players;
vector<vector<ll>> dist_to_nearest_player; // dystans do najbliższego zawodnika
vector<vector<pair<int,ll>>> graph; // < v, d >
vector<ll> dist;

bool legal_pos(int s, int t) {
	return 0 <= s && s <= H && 0 <= t && t <= W;
}

int pos_to_v(int s, int t) {
	return s * (W + 1) + t;
}

void print_dist() {
	for (int i=0; i<=H; i++) {
		for (int j=0; j<=W; j++) {
			cout << dist_to_nearest_player[i][j] << ' ';
		}
		cout << '\n';
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> H >> W;
	cin >> A >> B >> C;
	cin >> N;

	dist_to_nearest_player.assign(H+1, vector<ll>(W+1, INF));

	queue<pair<int,int>> Q;

	for (int i=0; i<N; i++) {
		int S, T;
		cin >> S >> T;
		players.push_back({ S, T });
		Q.push({ S, T });
		dist_to_nearest_player[S][T] = 0;
	}

	vector<pair<int,int>> moves = { {-1,0}, {1,0}, {0,-1}, {0,1} };
	while (!Q.empty()) {
		const auto& [s, t] = Q.front(); Q.pop();
		for (const auto& [ds, dt]: moves) if (legal_pos(s+ds, t+dt)) {
			if (dist_to_nearest_player[s+ds][t+dt] <= dist_to_nearest_player[s][t] + 1) continue;
			dist_to_nearest_player[s+ds][t+dt] = dist_to_nearest_player[s][t] + 1;
			Q.push({ s+ds, t+dt });
		}
	}

	int cnt_fields = (H+1) * (W+1);
	dist.assign(cnt_fields * 5, INF);

	graph.assign((cnt_fields+1)*5, vector<pair<int,ll>>());

	for (int i=0; i<4; i++) {
		const auto& [ds, dt] = moves[i];
		for (int s=0; s<=H; s++) for (int t=0; t<=W; t++) if (legal_pos(s+ds,t+dt)) {
			graph[cnt_fields * i + pos_to_v(s,t)].push_back({ cnt_fields * i + pos_to_v(s+ds,t+dt), A });
			graph[cnt_fields * 4 + pos_to_v(s,t)].push_back({ cnt_fields * 4 + pos_to_v(s+ds,t+dt), C });
		}
	}

	for (int i=0; i<4; i++) for (int s=0; s<=H; s++) for (int t=0; t<=W; t++) {
		graph[cnt_fields * 4 + pos_to_v(s,t)].push_back({ cnt_fields * i + pos_to_v(s,t), B });
		graph[cnt_fields * i + pos_to_v(s,t)].push_back({ cnt_fields * 4 + pos_to_v(s,t), dist_to_nearest_player[s][t] * C });
	}

	priority_queue<pair<ll,int>> PQ; // < -dist, v >
	int start_v = cnt_fields * 4 + pos_to_v(players[0].first, players[0].second);
	int target_v = cnt_fields * 4 + pos_to_v(players[N-1].first, players[N-1].second);
	dist[start_v] = 0;
	PQ.push({ 0, start_v });
	while (!PQ.empty()) {
		const int v = PQ.top().second; PQ.pop();
		for (const auto& [u, d]: graph[v]) {
			if (dist[v] + d >= dist[u]) continue;
			dist[u] = dist[v] + d;
			PQ.push({ -dist[u], u });
		}
	}

	cout << dist[target_v] << '\n';
}

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