Submission #332179

#	Time	Username	Problem	Language	Result	Execution time	Memory
332179		arnold518	Soccer (JOI17_soccer)	C++14	100 / 100	1744 ms	39364 KiB

soccer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXH = 500;
const int MAXN = 1e5;
const ll INF = 1e18;

const int dy[]={-1, 1, 0, 0};
const int dx[]={0, 0, -1, 1};

int H, W, N;
ll A, B, C;
pii P[MAXN+10];

ll D[MAXH+10][MAXH+10];
ll dist[MAXH+10][MAXH+10][5];

struct Queue
{
	int y, x, k; ll w;
	bool operator < (const Queue &p) const
	{
		return w>p.w;
	}
};

int main()
{
	scanf("%d%d", &H, &W);
	scanf("%lld%lld%lld", &A, &B, &C);
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d%d", &P[i].first, &P[i].second);

	queue<pii> Q;
	for(int i=0; i<=H; i++) for(int j=0; j<=W; j++) D[i][j]=INF;
	for(int i=1; i<=N; i++)
	{
		Q.push({P[i].first, P[i].second});
		D[P[i].first][P[i].second]=0;
	}
	while(!Q.empty())
	{
		pii now=Q.front(); Q.pop();
		for(int i=0; i<4; i++)
		{
			int ny=now.first+dy[i], nx=now.second+dx[i];
			if(!(0<=ny && ny<=H && 0<=nx && nx<=W)) continue;
			if(D[ny][nx]!=INF) continue;
			D[ny][nx]=D[now.first][now.second]+1;
			Q.push({ny, nx});
		}
	}

	priority_queue<Queue> PQ;
	PQ.push({P[1].first, P[1].second, 4, 0});

	for(int i=0; i<=H; i++) for(int j=0; j<=W; j++) for(int k=0; k<5; k++) dist[i][j][k]=INF;

	while(!PQ.empty())
	{
		Queue now=PQ.top(); PQ.pop();
		if(dist[now.y][now.x][now.k]<=now.w) continue;
		dist[now.y][now.x][now.k]=now.w;

		if(now.k==4)
		{
			for(int i=0; i<4; i++)
			{
				int ny=now.y+dy[i], nx=now.x+dx[i];
				if(!(0<=ny && ny<=H && 0<=nx && nx<=W)) continue;
				PQ.push({ny, nx, 4, now.w+C});
				PQ.push({ny, nx, i, now.w+A+B});
			}
		}
		else
		{
			int ny=now.y+dy[now.k], nx=now.x+dx[now.k];
			if(D[now.y][now.x]!=INF) PQ.push({now.y, now.x, 4, now.w+D[now.y][now.x]*C});
			if(!(0<=ny && ny<=H && 0<=nx && nx<=W)) continue;
			PQ.push({ny, nx, now.k, now.w+A});
		}
	}

	ll ans=INF;
	for(int i=0; i<5; i++) ans=min(ans, dist[P[N].first][P[N].second][i]);
	printf("%lld\n", ans);
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  scanf("%d%d", &H, &W);
      |  ~~~~~^~~~~~~~~~~~~~~~
soccer.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |  scanf("%lld%lld%lld", &A, &B, &C);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
soccer.cpp:36:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |  for(int i=1; i<=N; i++) scanf("%d%d", &P[i].first, &P[i].second);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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