Submission #335360

#	Time	Username	Problem	Language	Result	Execution time	Memory
335360		ChrisT	Soccer (JOI17_soccer)	C++17	100 / 100	989 ms	38340 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
struct State {
	long long d; int x,y,z;
	bool operator< (const State &o) const {
		return d > o.d;
	}
};
const int MN = 505;
long long dist[MN][MN][5];
int pre[MN][MN], dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
int main() {
	int n,m,a,b,c,k;
	scanf ("%d %d %d %d %d %d",&n,&m,&a,&b,&c,&k);
	queue<pair<int,int>> q; vector<pair<int,int>> bois(k);
	memset(pre,0x3f,sizeof pre);
	for (auto &[x,y] : bois) {
		scanf ("%d %d",&x,&y);
		pre[x][y] = 0; q.push({x,y});
	}
	while (!q.empty()) {
		auto [x,y] = q.front(); q.pop();
		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k], ny = y + dy[k];
			if (nx >= 1 && nx <= n && 1 <= ny && ny <= m && pre[x][y] + 1 < pre[nx][ny]) {
				pre[nx][ny] = pre[x][y] + 1;
				q.push({nx,ny});
			}
		}
	}
	memset(dist,0x3f,sizeof dist);
	auto [sx,sy] = bois[0];
	dist[sx][sy][0] = 0; 
	priority_queue<State> pq;
	pq.push({0,sx,sy,0});
	while (!pq.empty()) {
		auto [d,x,y,z] = pq.top(); pq.pop();
		if (d > dist[x][y][z]) continue;
		if (!z) {
			for (int k = 0; k < 4; k++) {
				int nx = x + dx[k], ny = y + dy[k];
				if (nx < 0 || nx > n || ny < 0 || ny > m) continue;
				if (d + c < dist[nx][ny][0]) {
					dist[nx][ny][0] = d + c;
					pq.push({d+c,nx,ny,0});
				}
				if (d + a < dist[nx][ny][k+1]) {
					dist[nx][ny][k+1] = d + a;
					pq.push({d+a,nx,ny,k+1});
				}
			}
		} else {
			if (d + b + (long long)a * pre[x][y] < dist[x][y][0]) {
				dist[x][y][0] = d + b + (long long)c * pre[x][y];
				pq.push({dist[x][y][0],x,y,0});
			}
			int nx = x + dx[z-1], ny = y + dy[z-1];
			if (nx >= 0 && nx <= n && ny >= 0 && ny <= m && d + a < dist[nx][ny][z]) {
				dist[nx][ny][z] = d + a;
				pq.push({d+a,nx,ny,z});
			} 
		}
	}
	auto [ex,ey] = bois.back();
	printf ("%lld\n",dist[ex][ey][0]);
	return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   14 |  scanf ("%d %d %d %d %d %d",&n,&m,&a,&b,&c,&k);
      |  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:18:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |   scanf ("%d %d",&x,&y);
      |   ~~~~~~^~~~~~~~~~~~~~~

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