Submission #837445

#	Time	Username	Problem	Language	Result	Execution time	Memory
837445		Liudas	Soccer (JOI17_soccer)	C++17	100 / 100	385 ms	27116 KiB

soccer

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node{
	int type;
	int val;
	int x, y;
	bool operator<(const node & a)const{
		return val > a.val;
	}
};
signed main(){
	int X, Y, A, B, C, N;
	cin >> X >> Y >> A >> B >> C >> N;
	vector<pair<int,int>> players(N);
	vector<vector<int>> pos(X + 10, vector<int>(Y + 10, 1e9));
	queue<array<int, 3>> populate;
	for(int i = 0; i < N; i ++){
		cin >> players[i].first >> players[i].second;
		populate.push({players[i].first, players[i].second, 0});
	}
	while(!populate.empty()){
		int x = populate.front()[0], y = populate.front()[1], c = populate.front()[2];
		populate.pop();
		if(pos[x][y] <= c)continue;
		if(x > 0)populate.push({x - 1, y , c+ 1});
		if(y > 0)populate.push({x, y-1, c+1});
		if(x < X)populate.push({x + 1, y, c + 1});
		if(y < Y)populate.push({x, y + 1, c + 1});
		pos[x][y] = c;
	} 
	vector<vector<vector<int>>> arr(X + 5, vector<vector<int>>(Y + 5, vector<int>(3, 1e17)));
	arr[players[0].first][players[0].second][2] = 0;
	priority_queue<node> que;
	que.push({2, 0, players[0].first,players[0].second});
	while(!que.empty()){
		node a = que.top();
		que.pop();
		if(arr[a.x][a.y][a.type] != a.val)continue;
		if(a.type == 2){
			if(a.x > 0 && arr[a.x-1][a.y][2] > a.val + C){que.push({2, a.val+C, a.x-1, a.y});arr[a.x-1][a.y][2] = a.val+C;}
			if(a.y > 0 && arr[a.x][a.y-1][2] > a.val + C){que.push({2, a.val+C, a.x, a.y-1});arr[a.x][a.y-1][2] = a.val+C;}
			if(a.x < X && arr[a.x+1][a.y][2] > a.val + C){que.push({2, a.val+C, a.x+1, a.y});arr[a.x+1][a.y][2] = a.val+C;}
			if(a.y < Y && arr[a.x][a.y+1][2] > a.val + C){que.push({2, a.val+C, a.x, a.y+1});arr[a.x][a.y+1][2] = a.val+C;}

			if(a.val + B < arr[a.x][a.y][0]){que.push({0, a.val+B, a.x, a.y});arr[a.x][a.y][0] = a.val+B;}
			if(a.val + B < arr[a.x][a.y][1]){que.push({1, a.val+B, a.x, a.y});arr[a.x][a.y][1] = a.val+B;}
		}
		if(a.type == 1){
			if(a.y > 0 && arr[a.x][a.y - 1][1] > a.val + A){que.push({1, a.val+A, a.x, a.y - 1});arr[a.x][a.y - 1][1] = a.val+A;}
			if(a.y < Y && arr[a.x][a.y + 1][1] > a.val + A){que.push({1, a.val+A, a.x, a.y + 1});arr[a.x][a.y + 1][1] = a.val+A;}
			if(a.val + pos[a.x][a.y] * C < arr[a.x][a.y][2]){que.push({2, a.val + pos[a.x][a.y] * C, a.x, a.y}); arr[a.x][a.y][2] = a.val + pos[a.x][a.y] * C;}
		}
		if(a.type == 0){
			if(a.x > 0 && arr[a.x - 1][a.y][0] > a.val + A){que.push({0, a.val+A, a.x - 1, a.y});arr[a.x - 1][a.y][0] = a.val+A;}
			if(a.x < X && arr[a.x + 1][a.y][0] > a.val + A){que.push({0, a.val+A, a.x + 1, a.y});arr[a.x + 1][a.y][0] = a.val+A;}
			if(a.val + pos[a.x][a.y] * C < arr[a.x][a.y][2]){que.push({2, a.val + pos[a.x][a.y] * C, a.x, a.y}); arr[a.x][a.y][2] = a.val + pos[a.x][a.y] * C;}
		}
	}
	cout << arr[players.back().first][players.back().second][2] << endl;
	return 0;
}

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