Submission #206617

#	Time	Username	Problem	Language	Result	Execution time	Memory
206617		opukittpceno_hhr	Soccer (JOI17_soccer)	C++17	30 / 100	1796 ms	8312 KiB

soccer

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <random>

using namespace std;

#define int long long

const int INF = 1e18 + 239;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int h, w, a, b, c, n;
	cin >> h >> w >> a >> b >> c >> n;
	h++;
	w++;
	vector<int> s(n);
	vector<int> t(n);
	for (int i = 0; i < n; i++) {
		cin >> s[i] >> t[i];
	}
	auto cost = [&](int i, int j) {
		if (i == j) return (int)0;
		//move i
		int ans = INF;
		for (int tj = 0; tj < w; tj++) {
			int mi = s[j];
			int mj = tj;
			int cur = c * (abs(s[i] - mi) + abs(t[i] - mj)) + b + a * (abs(mi - s[j]));
			if (mi == s[j] && mj == t[j]) cur -= b;

			ans = min(ans, cur);
		}
		for (int ti = 0; ti < h; ti++) {
			int mi = ti;
			int mj = t[j];
			int cur = c * (abs(s[i] - mi) + abs(t[i] - mj)) + b + a * (abs(mj - t[j]));
			if (mi == s[j] && mj == t[j]) cur -= b;
			ans = min(ans, cur);
		}
		return ans;
	};
	vector<vector<int>> d(n, vector<int> (n, INF));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			d[i][j] = cost(i, j);
		}
	}
	vector<int> used(n);
	vector<int> rd(n, INF);
	rd[0] = 0;
	for (int it = 0; it < n; it++) {
		int who = -1;
		for (int i = 0; i < n; i++) {
			if (used[i]) continue;
			if (who == -1 || rd[who] > rd[i]) who = i;
		}
		used[who] = 1;
		for (int j = 0; j < n; j++) {
			rd[j] = min(rd[j], rd[who] + d[who][j]);
		}
	}
	cout << rd[n - 1] << endl;
}

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