제출 #1281176

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281176		third	Soccer (JOI17_soccer)	C++20	35 / 100	34 ms	4860 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;
}

void pre() {
	queue<pii> q;
	for (int i = 1; i <= n; i ++) {
		ll u = a[i].fi, v = a[i].se;
		vst[u][v] = 1;
		q.push({u, v});
		dis[u][v] = 0;
	}
	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;
	}*/
}

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;
   	}
   	
   	pre();
   	
   	dij();
   	
   	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

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