Submission #1001184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001184		aykhn	Soccer (JOI17_soccer)	C++17	100 / 100	391 ms	27188 KiB

soccer

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

const int MXN = 5e2 + 5;

int h, w;
int d[5][MXN][MXN];
int d1[MXN][MXN];

int A[4] = {0, 0, -1, 1}, B[4] = {-1, 1, 0, 0};

int ok(int x, int y)
{
	return (x >= 0 && x <= h && y >= 0 && y <= w);
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	for (int i = 0; i < MXN; i++) 
	{
		for (int j = 0; j < MXN; j++) 
		{
			d1[i][j] = inf;
			for (int k = 0; k < 5; k++) d[k][i][j] = inf;
		}
	}
	cin >> h >> w;
	int a, b, c;
	cin >> a >> b >> c;
	int n;
	cin >> n;
	priority_queue<array<int, 4>, vector<array<int, 4>>, greater<array<int, 4>>> pq;
	priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq1;
	array<int, 2> cor[n];
	for (int i = 0; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		cor[i] = {x, y};
		d1[x][y] = 0;
		pq1.push({0, x, y});
	}
	while (!pq1.empty())
	{
		int W = pq1.top()[0], x = pq1.top()[1], y = pq1.top()[2];
		pq1.pop();
		if (d1[x][y] < W) continue;
		for (int i = 0; i < 4; i++)
		{
			int x1 = x + A[i], y1 = y + B[i];
			if (ok(x1, y1) && d1[x1][y1] > W + c)
			{
				d1[x1][y1] = W + c;
				pq1.push({d1[x1][y1], x1, y1});
			}
		}
	}
	pq.push({0, 4, cor[0][0], cor[0][1]});
	d[4][cor[0][0]][cor[0][1]] = 0;
	while (!pq.empty())
	{
		int W = pq.top()[0], t = pq.top()[1], x = pq.top()[2], y = pq.top()[3];
		pq.pop();
		if (d[t][x][y] < W) continue;
		if (d[4][x][y] > W + d1[x][y])
		{
			d[4][x][y] = W + d1[x][y];
			pq.push({d[4][x][y], 4, x, y});
		}
		if (t == 4)
		{
			for (int i = 0; i < 4; i++)
			{
				int x1 = x + A[i], y1 = y + B[i];
				if (ok(x1, y1) && d[4][x1][y1] > W + c)
				{
					d[4][x1][y1] = W + c;
					pq.push({d[4][x1][y1], 4, x1, y1});
				}
				if (ok(x1, y1) && d[i][x1][y1] > W + c)
				{
					d[i][x1][y1] = W + b + a;
					pq.push({d[i][x1][y1], i, x1, y1});
				}
			}
		}
		else
		{
			int x1 = x + A[t], y1 = y + B[t];
			if (ok(x1, y1) && d[t][x1][y1] > W + a)
			{
				d[t][x1][y1] = W + a;
				pq.push({d[t][x1][y1], t, x1, y1});
			}
		}
	}
	int res = inf;
	for (int i = 0; i < 5; i++) res = min(res, d[i][cor[n - 1][0]][cor[n - 1][1]]);
	cout << res << '\n';
}

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