Submission #681914

#	Time	Username	Problem	Language	Result	Execution time	Memory
681914		Kahou	Soccer (JOI17_soccer)	C++14	100 / 100	681 ms	30932 KiB

soccer

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll inf = 1e18 + 50;
const int N = 550, M = 1e5 + 50;
ll n, h, w, A, B, C;
pll P[M];
ll dis[N][N][6], bdis[N][N];
queue<pll> q;
set<pll> st;
int dx[] = {0, 1, 0,-1};
int dy[] = {1, 0,-1, 0};


inline ll f(int x, int y, int c) {
	return x*N*6 + y*6 + c;
}

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

void solve() {
	cin >> h >> w;
	cin >> A >> B >> C;
	cin >> n;
	for (int x = 0; x <= h; x++) {
		for (int y = 0; y <= w; y++) {
			bdis[x][y] = inf;
			for (int c = 0; c < 6; c++) {
				dis[x][y][c] = inf;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cin >> P[i].F >> P[i].S;
		if (i < n) {
			bdis[P[i].F][P[i].S] = 0;
			q.push(P[i]);
		}
	}

	if (n == 1) {
		cout << 0 << endl;
		return;
	}

	while (q.size()) {
		int x = q.front().F, y = q.front().S;
		q.pop();
		for (int i = 0; i < 4; i++) {
			if (val(x+dx[i], y+dy[i]) && bdis[x][y]+C < bdis[x+dx[i]][y+dy[i]]) {
				bdis[x+dx[i]][y+dy[i]] = bdis[x][y]+C;
				q.push({x+dx[i], y+dy[i]});
			}
		}
	}
	dis[P[1].F][P[1].S][5] = 0;
	st.insert({0, f(P[1].F, P[1].S, 5)});
	while (st.size()) {
		ll x = st.begin()->S/(N*6), y = (st.begin()->S/6)%N, c = (st.begin()->S%6);
		st.erase(st.begin());
		if (c == 0) {
			if (dis[x][y][0] + bdis[x][y] < dis[x][y][5]) {
				st.erase({dis[x][y][5], f(x, y, 5)});
				dis[x][y][5] = dis[x][y][0] + bdis[x][y];
				st.insert({dis[x][y][5], f(x, y, 5)});
			}
		}
		else if (c == 5) {
			if (dis[x][y][5] < dis[x][y][0]) {
				st.erase({dis[x][y][0], f(x, y, 0)});
				dis[x][y][0] = dis[x][y][5];
				st.insert({dis[x][y][0], f(x, y, 0)});
			}
			for (int i = 0; i < 4; i++) {
				if (dis[x][y][5] + B < dis[x][y][i+1]) {
					st.erase({dis[x][y][i+1], f(x, y, i+1)});
					dis[x][y][i+1] = dis[x][y][5] + B;
					st.insert({dis[x][y][i+1], f(x, y, i+1)});
				}
				ll xp = x+dx[i], yp = y+dy[i];
				if (!val(xp, yp)) continue;
				if (dis[x][y][5] + C < dis[xp][yp][5]) {
					st.erase({dis[xp][yp][5], f(xp, yp, 5)});
					dis[xp][yp][5] = dis[x][y][5] + C;
					st.insert({dis[xp][yp][5], f(xp, yp, 5)});
				}
			}
		}
		else {
			if (dis[x][y][c] < dis[x][y][0]) {
				st.erase({dis[x][y][0], f(x, y, 0)});
				dis[x][y][0] = dis[x][y][c];
				st.insert({dis[x][y][0], f(x, y, 0)});
			}
			ll xp = x+dx[c-1], yp = y+dy[c-1];
			if (!val(xp, yp)) continue;
			if (dis[x][y][c] + A < dis[xp][yp][c]) {
				st.erase({dis[xp][yp][c], f(xp, yp, c)});
				dis[xp][yp][c] = dis[x][y][c] + A;
				st.insert({dis[xp][yp][c], f(xp, yp, c)});
			}
		}
	}
	cout << dis[P[n].F][P[n].S][0] << endl;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}

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