Submission #991935

#	Time	Username	Problem	Language	Result	Execution time	Memory
991935		horezushol	Soccer (JOI17_soccer)	C++14	35 / 100	46 ms	21408 KiB

soccer

#include<bits/stdc++.h>
#define debug(x) cout << "\033[36m"<< __LINE__ << ":\033[39m "  << (#x) << " = " << (x) << '\n'

#define F first
#define S second

const char nl = '\n';

using namespace std;
using ll = long long;

const ll N = 1e5+10;
ll h, w, A, B, C, n;
vector<pair<ll, ll>> vp(N);

vector<pair<ll, ll>> g[N];
vector<ll> dist(N, LLONG_MAX);

 
ll go(ll x, ll y, ll X, ll Y) {
	return abs(x - X) + abs(y - Y);
}
 
ll shoot(ll x, ll y, ll X, ll Y) {
	ll res1 = abs(x - X)*C;
	ll res2 = abs(y - Y)*C;
	res1 += A*go(X, y, X, Y) + B;
	res2 += A*go(x, Y, X, Y) + B;
	return min(res1, res2);
}


void dij(ll x) {
	set<pair<ll, ll>> q;
	q.insert({0, x});
	dist[x] = 0;
	while (!q.empty()) {
		ll to = q.begin() -> S;
		q.erase(q.begin());
		for (auto el : g[to]) {
			ll L = el.F, R = el.S;
			if (dist[L] > dist[to] + R) {
				q.erase({dist[L], L});
				dist[L] = dist[to] + R;
				q.insert({dist[L], L});
			}
		}
	}
}

void solve() {
	cin >> h >> w >> A >> B >> C >> n;
	for (ll i = 1; i <= n; i ++) {
		cin >> vp[i].F >> vp[i].S;
	}
	for (ll i = 1; i <= n; i ++) {
		for (ll j = i+1; j <= n; j ++) {
			ll mn = shoot(vp[i].F, vp[i].S, vp[j].F, vp[j].S);
			mn = min(mn, go(vp[i].F, vp[i].S, vp[j].F, vp[j].S) * C);
			g[i].push_back({j, mn});
			g[j].push_back({i, mn});
		}
	}
	dij(1);
	cout << dist[n];
	// for (ll i = 1; i <= n; i ++) {
	// 	cout << i << ": ";
	// 	for (auto j : g[i]) {
	// 		cout << "[" << j.first << ", " << j.second << "] ";
	// 	}
	// 	cout << nl;
	// }
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll tst = 1;
	// cin >> tst;
	while (tst --) {
		solve();
		cout << nl;
	}
}

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