Submission #490996

#	Time	Username	Problem	Language	Result	Execution time	Memory
490996		Haruto810198	Soccer (JOI17_soccer)	C++17	100 / 100	955 ms	145932 KiB

soccer

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 510;

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

// 0, 1, 2, 3, 4 : D, U, R, L, X

int h, w;
int A, B, C;
int n;
pii pt[100010];

int dis[MAX][MAX];
int id[MAX][MAX];

vector<pii> edge[5 * MAX * MAX];
int res[5 * MAX * MAX];

void bfs(){
	
	FOR(i, 0, h, 1){
		FOR(j, 0, w, 1){
			dis[i][j] = INF;
		}
	}

	queue<pii> qu;
	
	FOR(i, 1, n, 1){
		dis[pt[i].F][pt[i].S] = 0;
		qu.push(pt[i]);
	}
	
	while(!qu.empty()){
		pii v = qu.front();
		qu.pop();
		int vx = v.F, vy = v.S;
		FOR(i, 0, 3, 1){
			int ux = vx + dx[i], uy = vy + dy[i];
			if(0 <= ux and ux <= h and 0 <= uy and uy <= w and dis[ux][uy] == INF){
				dis[ux][uy] = dis[vx][vy] + 1;
				qu.emplace(ux, uy);
			}
		}
	}
	
}

void Dijkstra(){
	
	FOR(i, 0, 5 * (h + 1) * (w + 1), 1){
		res[i] = LNF;
	}
	res[ 5 * id[ pt[1].F ][ pt[1].S ] + 4 ] = 0; // pt[1], stop
	
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.emplace(0, 5 * id[ pt[1].F ][ pt[1].S ] + 4);
	
	while(!pq.empty()){
		int v = pq.top().S;
		int resv = pq.top().F;
		pq.pop();
		
		if(resv > res[v]) continue;
		
		for(pii e : edge[v]){
			int u = e.F;
			int duv = e.S;
			if(res[v] + duv < res[u]){
				res[u] = res[v] + duv;
				pq.emplace(res[u], u);
			}
		}
	}

}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
	cin>>h>>w;
	cin>>A>>B>>C;
	cin>>n;
	FOR(i, 1, n, 1){
		cin>>pt[i].F>>pt[i].S;
	}
	
	bfs();
	/*
	cerr<<"dis : "<<endl;
	FOR(i, 0, h, 1){
		FOR(j, 0, w, 1){
			cerr<<dis[i][j]<<" ";
		}
		cerr<<endl;
	}
	cerr<<endl;
	*/
	FOR(i, 0, h, 1){
		FOR(j, 0, w, 1){
			id[i][j] = i * (w + 1) + j;
		}
	}

	FOR(i, 0, h, 1){
		FOR(j, 0, w, 1){

			int v = id[i][j];
			
			// v, move -> u, move
			// v, stop -> u, stop
			FOR(k, 0, 3, 1){
				int ii = i + dx[k], jj = j + dy[k];
				if(!(0 <= ii and ii <= h and 0 <= jj and jj <= w)) continue;
				int u = id[ii][jj];
				edge[5*v + k].eb(5*u + k, A);
				edge[5*v + 4].eb(5*u + 4, C);
			}

			// v, move -> v, stop
			FOR(k, 0, 3, 1){
				edge[5*v + k].eb(5*v + 4, 0);
			}

			// v, stop -> v, move
			FOR(k, 0, 3, 1){
				edge[5*v + 4].eb(5*v + k, dis[i][j] * C + B);
			}
		}
	}
	
	Dijkstra();
	
	int Res = LNF;
	FOR(k, 0, 4, 1){
		// pt[n]
		Res = min(Res, res[5 * id[ pt[n].F ][ pt[n].S ] + k]);
	}
	cout<<Res<<'\n';
	
	return 0;
	
}

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