Submission #1281298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281298		third	Soccer (JOI17_soccer)	C++20	5 / 100	459 ms	327680 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;

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;

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());
	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];

struct Node {
	ll c, x, y, t;
};

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 ++) {
				d1[i][j][z] = inf;
			}
		}
	}
	d1[a[1].fi][a[1].se][1] = 0;
	pq.push({d1[a[1].fi][a[1].se][1], a[1].fi, a[1].se, 1});
	while (pq.size()) {
		ll c = pq.top().c;
		pii u = {pq.top().x, pq.top().y};
		ll tt = pq.top().t;
		//cout << u.fi << " " << u.se << " " << tt << " " << c << endl;
		pq.pop();
		if (c > d1[u.fi][u.se][tt]) continue;
		ll need = dis[u.fi][u.se] * C;
		if (tt == 1) need = 0;
		for (auto it : px) {
			pii pos = {it, u.se};
			ll n_val = need + kc(pos, u) * C;// tu re bong den
			if (d1[pos.fi][pos.se][1] > c + n_val) {
				d1[pos.fi][pos.se][1] = c + n_val;
				pq.push({d1[pos.fi][pos.se][1], pos.fi, pos.se, 1});
			}
			n_val = need + kc(pos, u) * A + B;
			if (d1[pos.fi][pos.se][0] > c + n_val) {
				d1[pos.fi][pos.se][0] = c + n_val;
				pq.push({d1[pos.fi][pos.se][0], pos.fi, pos.se, 0});
			}
		}
		for (auto it : py) {
			pii pos = {u.fi, it};
			ll n_val = need + kc(pos, u) * C;// tu re bong den
			if (d1[pos.fi][pos.se][1] > c + n_val) {
				d1[pos.fi][pos.se][1] = c + n_val;
				pq.push({d1[pos.fi][pos.se][1], pos.fi, pos.se, 1});
			}
			n_val = need + kc(pos, u) * A + B;
			if (d1[pos.fi][pos.se][0] > c + n_val) {
				d1[pos.fi][pos.se][0] = c + n_val;
				pq.push({d1[pos.fi][pos.se][0], pos.fi, pos.se, 0});
			}
		}
	}
}

void sub2() {
	pre();
	dij2();
	ll ans = min(d1[a[n].fi][a[n].se][0], d1[a[n].fi][a[n].se][1]);
	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: 0 / 30
• Subtask 3: 0 / 65