Submission #837333

#	Time	Username	Problem	Language	Result	Execution time	Memory
837333		gustason	Soccer (JOI17_soccer)	C++14	100 / 100	223 ms	18400 KiB

soccer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll

const ll INF = 1e16 + 5;
const int INF2 = 1e9 + 5;

int dist[501][501];
ll cost[3][501][501];

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

struct Vertex {
	int type, x, y;
	ll cost;
	bool operator<(const Vertex& other) const {
		return cost > other.cost;
	}
};

void fill() {
	for(int i = 0; i < 501; i++) {
		for(int j = 0; j < 501; j++) {
			dist[i][j] = INF2;
			for(int k = 0; k < 3; k++) {
				cost[k][i][j] = INF;
			}
		}
	}
}

void flood(const vector<array<int, 2>>& p) {
	queue<array<int, 2>> q;
	for(auto& i : p) {
		dist[i[0]][i[1]] = 0;
		q.push({i[0], i[1]});
	}
	
	while(!q.empty()) {
		auto v = q.front();
		q.pop();
		
		for(int d = 0; d < 4; d++) {
			int X = v[0] + dx[d];
			int Y = v[1] + dy[d];
			if (!(X >= 0 && X <= 500 && Y >= 0 && Y <= 500)) continue;
			
			if (dist[v[0]][v[1]] + 1 < dist[X][Y]) {
				dist[X][Y] = dist[v[0]][v[1]] + 1;
				q.push({X, Y});
			}
		}
	}
}

void mini(int& a, int b) {
	a = min(a, b);
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int H, W, A, B, C;
	cin >> H >> W >> A >> B >> C;
	
	auto gali = [&](int X, int Y) {
		return (X >= 0 && X <= H && Y >= 0 && Y <= W);
	};
	
	int n;
	cin >> n;
	
	fill();
	
	vector<array<int, 2>> p(n);
	for(auto& i : p) {
		cin >> i[0] >> i[1];
	}
	
	//for(int i = 0; i <= H; i++) {
		//for(int j = 0; j <= W; j++) {
			//for(int k = 0; k < n; k++) {
				//dist[i][j] = min(dist[i][j], abs(p[k][0] - i) + abs(p[k][1] - j));
			//}
		//}
	//}
	flood(p);
	
	priority_queue<Vertex> q;
	q.push({2, p[0][0], p[0][1], 0});
	cost[2][p[0][0]][p[0][1]] = 0;

	while(!q.empty()) {
		auto v = q.top();
		q.pop();
		
		//cout << v.type << " " << v.cost << " " << v.x << " " << v.y << "\n";
		
		if (v.cost != cost[v.type][v.x][v.y]) continue;
		
		// moving w/ ball
		if (v.type == 2) {
			if (v.cost + B < cost[0][v.x][v.y]) {
				cost[0][v.x][v.y] = v.cost + B;
				q.push({0, v.x, v.y, v.cost + B});
			}
			if (v.cost + B < cost[1][v.x][v.y]) {
				cost[1][v.x][v.y] = v.cost + B;
				q.push({1, v.x, v.y, v.cost + B});
			}
			
			for(int d = 0; d < 4; d++) {
				int X = v.x + dx[d];
				int Y = v.y + dy[d];
				
				if (!gali(X, Y)) continue; 
				
				if (v.cost + C < cost[2][X][Y]) {
					cost[2][X][Y] = v.cost + C;
					q.push({2, X, Y, v.cost + C});
				}
			}
		}
		// kick in x
		else if (v.type == 1) {
			if (gali(v.x+1, v.y) && v.cost + A < cost[1][v.x+1][v.y]) {
				cost[1][v.x+1][v.y] = v.cost + A;
				q.push({1, v.x+1, v.y, v.cost + A});
			}
			if (gali(v.x-1, v.y) && v.cost + A < cost[1][v.x-1][v.y]) {
				cost[1][v.x-1][v.y] = v.cost + A;
				q.push({1, v.x-1, v.y, v.cost + A});
			}
			if (v.cost + C * dist[v.x][v.y] < cost[2][v.x][v.y]) {
				cost[2][v.x][v.y] = v.cost + C * dist[v.x][v.y];
				q.push({2, v.x, v.y, v.cost + C * dist[v.x][v.y]});
			}
		}
		// kick in Y
		else {
			if (gali(v.x, v.y+1) && v.cost + A < cost[0][v.x][v.y+1]) {
				cost[0][v.x][v.y+1] = v.cost + A;
				q.push({0, v.x, v.y+1, v.cost + A});
			}
			if (gali(v.x, v.y-1) && v.cost + A < cost[0][v.x][v.y-1]) {
				cost[0][v.x][v.y-1] = v.cost + A;
				q.push({0, v.x, v.y-1, v.cost + A});
			}
			if (v.cost + C * dist[v.x][v.y] < cost[2][v.x][v.y]) {
				cost[2][v.x][v.y] = v.cost + C * dist[v.x][v.y];
				q.push({2, v.x, v.y, v.cost + C * dist[v.x][v.y]});
			}
		}
	}
	
	cout << cost[2][p.back()[0]][p.back()[1]] << "\n";
	//for(int i = 0; i < n; i++) {
		//cout << cost[2][p[i][0]][p[i][1]] << "\n";
	//}
}

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