Submission #26938

#	Time	Username	Problem	Language	Result	Execution time	Memory
26938		kajebiii	Soccer (JOI17_soccer)	C++14	100 / 100	366 ms	25632 KiB

soccer

#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef tuple<int, int, int> ti;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_L = 5e2 + 10;

struct ND {
	ll d; pi p; int t;
	ND() {}
	ND(ll dd, pi pp, int tt) : d(dd), p(pp), t(tt) {}
	bool operator<(const ND &o) const{return d > o.d;}
};
int H, W, N; bool Vis[MAX_L][MAX_L][5];
ll A, B, C, Move[MAX_L][MAX_L], Dis[MAX_L][MAX_L][5];
pi St, En;
int main() {
	cin >> H >> W >> A >> B >> C >> N;
	for(int i=0; i<=H; i++) for(int j=0; j<=W; j++) {
		Move[i][j] = LINF;
		for(int k=0; k<5; k++) Dis[i][j][k] = LINF;
	}

	queue<pi> mQ;
	for(int i=0; i<N; i++) {
		int x, y; scanf("%d%d", &x, &y);
		if(i == 0) St = pi(x, y);
		if(i+1 == N) En = pi(x, y);
		mQ.push(pi(x, y));
		Move[x][y] = 0;
	}
	while(!mQ.empty()) {
		int x, y; tie(x, y) = mQ.front(); mQ.pop();
		for(int k=0; k<4; k++) {
			int nx = x + "1012"[k] - '1', ny = y + "0121"[k] - '1';
			if(nx < 0 || ny < 0 || nx > H || ny > W) continue;
			if(Move[nx][ny] > Move[x][y] + C) {
				Move[nx][ny] = Move[x][y] + C;
				mQ.push(pi(nx, ny));
			}
		}
	}
	priority_queue<ND> Q;
	Q.push(ND(0ll, St, 4)); Dis[St.one][St.two][4] = 0ll;
	while(!Q.empty()) {
		ND temp = Q.top(); Q.pop();
		ll d = temp.d; int x, y; tie(x, y) = temp.p; int t = temp.t;
		if(Vis[x][y][t]) continue; Vis[x][y][t] = true;
//		printf("%lld %d %d %d [%d %d]\n", d, x, y, t, En.one, En.two);
		if(x == En.one && y == En.two) {
			printf("%lld\n", d);
			return 0;
		}
		if(t == 4) {
			for(int k=0; k<4; k++) {
				int nx = x + "1012"[k] - '1', ny = y + "0121"[k] - '1';
				if(Dis[x][y][k] > d + B) Q.push(ND(Dis[x][y][k] = d+B, pi(x, y), k));
				if(nx < 0 || ny < 0 || nx > H || ny > W) continue;
				if(Dis[nx][ny][4] > d + C) Q.push(ND(Dis[nx][ny][4] = d+C, pi(nx, ny), 4));
			}
		} else {
			int nx = x + "1012"[t] - '1', ny = y + "0121"[t] - '1';
			if(!(nx < 0 || ny < 0 || nx > H || ny > W))
				if(Dis[nx][ny][t] > d + A) Q.push(ND(Dis[nx][ny][t] = d+A, pi(nx, ny), t));
			if(Dis[x][y][4] > d + Move[x][y]) Q.push(ND(Dis[x][y][4] = d + Move[x][y], pi(x, y), 4));
		}
	}
	return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:37:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
                                  ^

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