Submission #1302221

#TimeUsernameProblemLanguageResultExecution timeMemory
1302221vlomaczkSoccer (JOI17_soccer)C++20
100 / 100
254 ms26160 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

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

	ll H,W;
	cin >> H >> W;
	ll A,B,C;
	cin >> A >> B >> C;
	ll n; cin >> n;
	vector<ll> row(n), col(n);
	for(ll i=0; i<n; ++i) {
		cin >> row[i] >> col[i];
	}
	ll inf = 1e18;
	vector<vector<ll>> closest(H+1,vector<ll>(W+1, 1e6));	
	queue<pair<ll, ll>> Q;
	for(ll i=0; i<n-1; ++i) {
		Q.push({row[i], col[i]});
		closest[row[i]][col[i]] = 0;
	}
	auto chk = [&](ll r, ll c, ll d) {
		if(r < 0 || r > H || c < 0 || c > W) return;
		if(closest[r][c] < 1e6) return;
		closest[r][c] = d;
		Q.push({r,c});
	};
	while(Q.size()) {
		auto[r,c] = Q.front(); Q.pop();
		chk(r+1,c,closest[r][c]+1);
		chk(r-1,c,closest[r][c]+1);
		chk(r,c+1,closest[r][c]+1);
		chk(r,c-1,closest[r][c]+1);
	}
	vector<vector<vector<ll>>> dist(H+1, vector<vector<ll>>(W+1, vector<ll>(3, inf)));
	priority_queue<pair<ll, pair<pair<ll, ll>, ll>>> pq;
	auto check = [&](ll r, ll c, ll m, ll d) {
		if(r < 0 || r > H || c < 0 || c > W) return;
		if(dist[r][c][m] > d) {
			dist[r][c][m] = d;
			pq.push({-d, {{r,c},m}});
		}
	};
	dist[row[0]][col[0]][0] = 0;
	pq.push({0, {{row[0], col[0]}, 0}});
	while(pq.size()) {
		auto[dv, stat] = pq.top(); pq.pop();
		dv*=-1;
		auto[pos, mode] = stat;
		auto[r,c] = pos;
		if(dist[r][c][mode] != dv) continue;
		if(mode==0) {
			check(r+1, c, 0, dv+C);
			check(r-1, c, 0, dv+C);
			check(r, c+1, 0, dv+C);
			check(r, c-1, 0, dv+C);
			check(r, c, 1, dv+B);
			check(r, c, 2, dv+B);
		} else if(mode==1) {
			check(r+1, c, 1, dv+A);
			check(r-1, c, 1, dv+A);
		} else {
			check(r, c+1, 2, dv+A);
			check(r, c-1, 2, dv+A);
		}
		if(mode) check(r,c,0,dv + C*closest[r][c]);
	}
	ll r = row[n-1];
	ll c = col[n-1];
	cout << min(dist[r][c][0], min(dist[r][c][1], dist[r][c][2])) << "\n";


	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...