Submission #433144

#	Time	Username	Problem	Language	Result	Execution time	Memory
433144		rqi	Soccer (JOI17_soccer)	C++14	100 / 100	1006 ms	27576 KiB

soccer

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

typedef pair<int, int> pi;
typedef long long ll;
typedef vector<int> vi;

#define mp make_pair
#define f first
#define s second

#define sz(x) (int)(x).size()

const ll INF = 1e18;
const int MOD = 1e9+7;

const int mx = 505;

vi dx = vi{1, 0, -1, 0};
vi dy = vi{0, 1, 0, -1};

ll walking[mx][mx];
ll kicking[mx][mx][4];

int H, W;
ll A, B, C;

int N;
pi ST[100005];

bool isGood(pi a){
	return (0 <= a.f) && (a.f <= H) && (0 <= a.s) && (a.s <= W);
}

int closest_dist[mx][mx];

void genClosestDist(){
	for(int i = 0; i <= H; i++){
		for(int j = 0; j <= W; j++){
			closest_dist[i][j] = MOD;
		}
	}
	queue<pair<int, pi>> q;
	for(int i = 1; i <= N; i++){
		closest_dist[ST[i].f][ST[i].s] = 0;
		q.push(mp(0, ST[i]));
	}
	while(sz(q)){
		pair<int, pi> a = q.front(); q.pop();
		pi cur_pos = a.s;
		int dist = a.f;
		if(closest_dist[cur_pos.f][cur_pos.s] < dist) continue;
		for(int d = 0; d < 4; d++){
			pi new_pos = mp(cur_pos.f+dx[d], cur_pos.s+dy[d]);
			if(!isGood(new_pos)) continue;
			int new_dist = dist+1;
			if(closest_dist[new_pos.f][new_pos.s] > new_dist){
				closest_dist[new_pos.f][new_pos.s] = new_dist;
				q.push(mp(new_dist, new_pos));
			}
		}
	}
}

int main(){
	cin >> H >> W;
	cin >> A >> B >> C;
	cin >> N;
	for(int i = 1; i <= N; i++){
		cin >> ST[i].f >> ST[i].s;
	}
	genClosestDist();

	for(int i = 0; i <= H; i++){
		for(int j = 0; j <= W; j++){
			for(int d = 0; d < 4; d++){
				kicking[i][j][d] = INF;
			}
			walking[i][j] = INF;
		}
	}
	
	priority_queue<pair<ll, vi>, vector<pair<ll, vi>>, greater<pair<ll, vi>>> pq;
	walking[ST[1].f][ST[1].s] = 0;
	pq.push(mp(0, vi{0, ST[1].f, ST[1].s})); //type 0 is walking, 1 is kicking

	while(sz(pq)){
		ll dist = pq.top().f;
		vi state = pq.top().s;
		pi cur_pos = mp(state[1], state[2]);
		pq.pop();
		if(state[0] == 0){ //walking
			if(walking[cur_pos.f][cur_pos.s] < dist) continue;
			for(int d = 0; d < 4; d++){
				pi new_pos = mp(cur_pos.f+dx[d], cur_pos.s+dy[d]);
				ll new_dist = dist+C;
				if(!isGood(new_pos)) continue;
				if(walking[new_pos.f][new_pos.s] <= new_dist) continue;
				walking[new_pos.f][new_pos.s] = new_dist;
				pq.push(mp(new_dist, vi{0, new_pos.f, new_pos.s}));
			}
			for(int d = 0; d < 4; d++){
				ll new_dist = dist+B;
				if(kicking[cur_pos.f][cur_pos.s][d] > new_dist){
					kicking[cur_pos.f][cur_pos.s][d] = new_dist;
					pq.push(mp(new_dist, vi{1, cur_pos.f, cur_pos.s, d}));
				}
			}
			
		}
		else{
			int cur_dir = state[3];
			if(kicking[cur_pos.f][cur_pos.s][cur_dir] < dist) continue;
			pi new_pos = mp(cur_pos.f+dx[cur_dir], cur_pos.s+dy[cur_dir]);
			if(isGood(new_pos)){
				ll new_dist = dist+A;
				if(kicking[new_pos.f][new_pos.s][cur_dir] > new_dist){
					kicking[new_pos.f][new_pos.s][cur_dir] = new_dist;
					pq.push(mp(new_dist, vi{1, new_pos.f, new_pos.s, cur_dir}));
				}	
			}
			ll new_dist = dist+C*closest_dist[cur_pos.f][cur_pos.s];
			if(walking[cur_pos.f][cur_pos.s] > new_dist){
				walking[cur_pos.f][cur_pos.s] = new_dist;
				pq.push(mp(new_dist, vi{0, cur_pos.f, cur_pos.s}));
			}
		}
	}
	cout << walking[ST[N].f][ST[N].s] << "\n";
}

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