Submission #1281318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281318		third	Soccer (JOI17_soccer)	C++20	100 / 100	675 ms	55696 KiB

soccer

#include<bits/stdc++.h>
typedef long long ll;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 100005
#define LOG 17
using namespace std;

const ll inf = 1e18;

// tu nghi

bool ghuy4g;

const ll hx[] = {1, -1, 0, 0};
const ll hy[] = {0, 0, 1, -1};

ll h, w, n, d[N], dis[505][505];
bool vst[505][505];
ll A, B, C;

pii a[N];

ll cal(ll i, ll j) {
	ll x = abs(a[i].fi - a[j].fi), y = abs(a[i].se - a[j].se);
	ll res = min({x * C + A * y + B, y * C + A * x + B, x * C + y * C});
	pii giao1 = {a[i].fi, a[j].se};
	res = min(res, min(y * C, A * y + B) + dis[giao1.fi][giao1.se] * C + A * x + B);
	pii giao2 = {a[j].fi, a[i].se};
	res = min(res, min(x * C, A * x + B) + dis[giao2.fi][giao2.se] * C + A * y + B);
	return res;
}

void dij() {
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	for (int i = 1; i <= n; i ++) {
		d[i] = inf;
	}
	d[1] = 0;
	pq.push({d[1], 1});
	while (pq.size()) {
		auto u = pq.top().se, c = pq.top().fi;
		pq.pop();
		if (c > d[u]) continue;
		for (int v = 1; v <= n; v ++) {
			if (u == v) continue;
			if (d[v] > c + cal(u, v)) {
				d[v] = c + cal(u, v);
				pq.push({d[v], v});
			}
		}
	}
	cout << d[n] << endl;
}

vector<ll> px, py;
ll pos_x[505], pos_y[505];

void pre() {
	queue<pii> q;
	for (int i = 1; i <= n; i ++) {
		ll u = a[i].fi, v = a[i].se;
		px.push_back(a[i].fi);
		py.push_back(a[i].se);
		vst[u][v] = 1;
		q.push({u, v});
		dis[u][v] = 0;
	}
	sort(px.begin(), px.end());
	px.resize(unique(px.begin(), px.end()) - px.begin());
	sort(py.begin(), py.end());
	py.resize(unique(py.begin(), py.end()) - py.begin());
	
	for (int i = 0; i < px.size(); i ++) {
		pos_x[px[i]] = i;
	}
	for (int i = 0; i < py.size(); i ++) {
		pos_y[py[i]] = i;
	}
	
	while (q.size()) {
		auto u = q.front(); q.pop();
		//cout << u.fi << " " << u.se << endl;
		for (int z = 0; z < 4; z ++) {
			ll dx = u.fi + hx[z];
			ll dy = u.se + hy[z];
			//cout << " " << dx << " " << dy << endl;
			if (dx > h || dy > w || dx < 0 || dy < 0 || vst[dx][dy]) continue;
			vst[dx][dy] = 1;
			dis[dx][dy] = dis[u.fi][u.se] + 1;
			q.push({dx, dy});
		}
	}
	/*for (int i = 0; i <= h; i ++) {
		for (int j = 0; j <= w; j ++) {
			cout << dis[i][j] << " ";
		}
		cout << endl;
	}*/
}

ll d1[505][505][2][2];

struct Node { // tt == 1: bong dang co ng giu
	ll c, x, y, t, nd; // nd == 0: ngang / nd == 1: doc
	// ta chi xet nd khi ma t == 0, tuc la bong dang ko co ng giu
};

struct CMP {
	bool operator() (const Node &a, const Node &b) const {
		return a.c > b.c;
	}
};

inline ll kc(pii a, pii b){
	return abs(a.fi - b.fi) + abs(a.se - b.se);
}

void dij2() {
	priority_queue<Node, vector<Node>, CMP> pq;
	for (int i = 0; i <= h; i ++) {
		for (int j = 0; j <= w; j ++) {
			for (int z = 0; z < 2; z ++) {
				for (int t = 0; t < 2; t ++) {
					d1[i][j][z][t] = inf;
				}
			}
		}
	}
	d1[a[1].fi][a[1].se][1][0] = 0;
	pq.push({d1[a[1].fi][a[1].se][1][0], a[1].fi, a[1].se, 1, 0});
	while (pq.size()) {
		ll c = pq.top().c;
		pii u = {pq.top().x, pq.top().y};
		ll t = pq.top().t;
		ll nd = pq.top().nd;
		//cout << u.fi << " " << u.se << " : " << t << " " << nd << " : " << c << endl;
		pq.pop();
		if (c > d1[u.fi][u.se][t][nd]) continue;
		ll need = dis[u.fi][u.se] * C;
		if (t == 1) need = 0;
		if (1) { // len va xuong cua nx
			auto it = pos_x[u.fi] + 1;
			if (0 <= it && it < px.size()) {
				pii pos = {px[it], u.se};
				ll n_val = need + kc(pos, u) * C;// tu re bong den
				if (d1[pos.fi][pos.se][1][0] > c + n_val) {
					d1[pos.fi][pos.se][1][0] = c + n_val;
					pq.push({d1[pos.fi][pos.se][1][0], pos.fi, pos.se, 1, 0});
				}
				n_val = need + kc(pos, u) * A + B;
				if (d1[pos.fi][pos.se][0][1] > c + n_val) {
					d1[pos.fi][pos.se][0][1] = c + n_val;
					pq.push({d1[pos.fi][pos.se][0][1], pos.fi, pos.se, 0, 1});
				}
				if (t == 0 && nd == 1) {
					if (d1[pos.fi][pos.se][0][1] > c + kc(pos, u) * A) {
						d1[pos.fi][pos.se][0][1] = c + kc(pos, u) * A;
						pq.push({d1[pos.fi][pos.se][0][1], pos.fi, pos.se, 0, 1});
					}
				}
			}
			it = pos_x[u.fi] - 1;
			if (0 <= it && it < px.size()) {
				pii pos = {px[it], u.se};
				ll n_val = need + kc(pos, u) * C;// tu re bong den
				if (d1[pos.fi][pos.se][1][0] > c + n_val) {
					d1[pos.fi][pos.se][1][0] = c + n_val;
					pq.push({d1[pos.fi][pos.se][1][0], pos.fi, pos.se, 1, 0});
				}
				n_val = need + kc(pos, u) * A + B;
				if (d1[pos.fi][pos.se][0][1] > c + n_val) {
					d1[pos.fi][pos.se][0][1] = c + n_val;
					pq.push({d1[pos.fi][pos.se][0][1], pos.fi, pos.se, 0, 1});
				}
				if (t == 0 && nd == 1) {
					if (d1[pos.fi][pos.se][0][1] > c + kc(pos, u) * A) {
						d1[pos.fi][pos.se][0][1] = c + kc(pos, u) * A;
						pq.push({d1[pos.fi][pos.se][0][1], pos.fi, pos.se, 0, 1});
					}
				}
			}
		}
		if (1) {
			auto it = pos_y[u.se] + 1;
			if (0 <= it && it < py.size()) {
				pii pos = {u.fi, py[it]};
				ll n_val = need + kc(pos, u) * C;// tu re bong den
				if (d1[pos.fi][pos.se][1][0] > c + n_val) {
					d1[pos.fi][pos.se][1][0] = c + n_val;
					pq.push({d1[pos.fi][pos.se][1][0], pos.fi, pos.se, 1, 0});
				}
				n_val = need + kc(pos, u) * A + B;
				if (d1[pos.fi][pos.se][0][0] > c + n_val) {
					d1[pos.fi][pos.se][0][0] = c + n_val;
					pq.push({d1[pos.fi][pos.se][0][0], pos.fi, pos.se, 0, 0});
				}
				if (t == 0 && nd == 0) {
					if (d1[pos.fi][pos.se][0][0] > c + kc(pos, u) * A) {
						d1[pos.fi][pos.se][0][0] = c + kc(pos, u) * A;
						pq.push({d1[pos.fi][pos.se][0][0], pos.fi, pos.se, 0, 0});
					}
				}
			}
			it = pos_y[u.se] - 1;
			if (0 <= it && it < py.size()) {
				pii pos = {u.fi, py[it]};
				ll n_val = need + kc(pos, u) * C;// tu re bong den
				if (d1[pos.fi][pos.se][1][0] > c + n_val) {
					d1[pos.fi][pos.se][1][0] = c + n_val;
					pq.push({d1[pos.fi][pos.se][1][0], pos.fi, pos.se, 1, 0});
				}
				n_val = need + kc(pos, u) * A + B;
				if (d1[pos.fi][pos.se][0][0] > c + n_val) {
					d1[pos.fi][pos.se][0][0] = c + n_val;
					pq.push({d1[pos.fi][pos.se][0][0], pos.fi, pos.se, 0, 0});
				}
				if (t == 0 && nd == 0) {
					if (d1[pos.fi][pos.se][0][0] > c + kc(pos, u) * A) {
						d1[pos.fi][pos.se][0][0] = c + kc(pos, u) * A;
						pq.push({d1[pos.fi][pos.se][0][0], pos.fi, pos.se, 0, 0});
					}
				}
			}
		}
	}
}

void sub2() {
	pre();
	dij2();
	ll ans = inf;
	for (int x = 0; x < 2; x ++){
		for (int y = 0; y < 2; y ++) {
			ans = min(ans, d1[a[n].fi][a[n].se][x][y]);
		}
	}
	cout << ans;
}

bool klinh;

signed main() {
   // freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	//srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
   	cin >> h >> w;
   	cin >> A >> B >> C;
   	
   	cin >> n;
   	for (int i = 1; i <= n; i ++) {
   		cin >> a[i].fi >> a[i].se;
   	}
   	
   	sub2();
   	
   	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

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