Submission #670571

#	Time	Username	Problem	Language	Result	Execution time	Memory
670571		S2speed	Soccer (JOI17_soccer)	C++17	100 / 100	416 ms	23604 KiB

soccer

#include<bits/stdc++.h>

using namespace std;

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;
typedef pair<pll , ll> plll;
typedef pair<ll , plll> pllll;

const ll maxn = 502 , inf = 2e18;

ll n , m , A , B , C;
ll dis[maxn][maxn][5];
short int f[maxn][maxn];
vector<pll> bfs;
priority_queue<pllll , vector<pllll> , greater<pllll>> pq;

void BFS(){
	ll x = 0;
	while(x < sze(bfs)){
		ll i = bfs[x].first , j = bfs[x++].second , hd = f[i][j] + 1;
		if(i > 0){
			if(f[i - 1][j] > hd){
				f[i - 1][j] = hd;
				bfs.push_back({i - 1 , j});
			}
		}
		if(j > 0){
			if(f[i][j - 1] > hd){
				f[i][j - 1] = hd;
				bfs.push_back({i , j - 1});
			}
		}
		if(i < n){
			if(f[i + 1][j] > hd){
				f[i + 1][j] = hd;
				bfs.push_back({i + 1 , j});
			}
		}
		if(j < m){
			if(f[i][j + 1] > hd){
				f[i][j + 1] = hd;
				bfs.push_back({i , j + 1});
			}
		}
	}
	return;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	memset(f , 63 , sizeof(f));
	memset(dis , 63 , sizeof(dis));
	ll k , x , y;
	cin>>n>>m>>A>>B>>C>>k;
	for(ll i = 0 ; i < k ; i++){
		cin>>x>>y;
		if(i == 0){
			dis[x][y][0] = 0;
			pq.push({0 , {{x , y} , 0}});
		}
		if(f[x][y] > 0) bfs.push_back({x , y});
		f[x][y] = 0;
	}
	BFS();
	while(!pq.empty()){
		pllll p = pq.top(); pq.pop();
		ll i = p.second.first.first , j = p.second.first.second , t = p.second.second;
		if(dis[i][j][t] != p.first) continue;
		if(t == 0){
			ll ps = dis[i][j][0] + B;
			if(dis[i][j][1] > ps){
				dis[i][j][1] = ps;
				pq.push({ps , {{i , j} , 1}});
			}
			if(dis[i][j][2] > ps){
				dis[i][j][2] = ps;
				pq.push({ps , {{i , j} , 2}});
			}
			if(dis[i][j][3] > ps){
				dis[i][j][3] = ps;
				pq.push({ps , {{i , j} , 3}});
			}
			if(dis[i][j][4] > ps){
				dis[i][j][4] = ps;
				pq.push({ps , {{i , j} , 4}});
			}
			ll dr = dis[i][j][0] + C;
			if(i > 0){
				if(dis[i - 1][j][0] > dr){
					dis[i - 1][j][0] = dr;
					pq.push({dr , {{i - 1 , j} , 0}});
				}
			}
			if(j > 0){
				if(dis[i][j - 1][0] > dr){
					dis[i][j - 1][0] = dr;
					pq.push({dr , {{i , j - 1} , 0}});
				}
			}
			if(i < n){
				if(dis[i + 1][j][0] > dr){
					dis[i + 1][j][0] = dr;
					pq.push({dr , {{i + 1 , j} , 0}});
				}
			}
			if(j < m){
				if(dis[i][j + 1][0] > dr){
					dis[i][j + 1][0] = dr;
					pq.push({dr , {{i , j + 1} , 0}});
				}
			}
		} else {
			ll rc = dis[i][j][t] + f[i][j] * C;
			if(dis[i][j][0] > rc){
				dis[i][j][0] = rc;
				pq.push({rc , {{i , j} , 0}});
			}
		}
		if(t == 1){
			ll ps = dis[i][j][1] + A;
			if(i > 0){
				if(dis[i - 1][j][1] > ps){
					dis[i - 1][j][1] = ps;
					pq.push({ps , {{i - 1 , j} , 1}});
				}
			}
		} else if(t == 2){
			ll ps = dis[i][j][2] + A;
			if(i < n){
				if(dis[i + 1][j][2] > ps){
					dis[i + 1][j][2] = ps;
					pq.push({ps , {{i + 1 , j} , 2}});
				}
			}
		} else if(t == 3){
			ll ps = dis[i][j][3] + A;
			if(j > 0){
				if(dis[i][j - 1][3] > ps){
					dis[i][j - 1][3] = ps;
					pq.push({ps , {{i , j - 1} , 3}});
				}
			}
		} else if(t == 4){
			ll ps = dis[i][j][4] + A;
			if(j < m){
				if(dis[i][j + 1][4] > ps){
					dis[i][j + 1][4] = ps;
					pq.push({ps , {{i , j + 1} , 4}});
				}
			}
		}
	}
	ll ans = inf;
	for(ll j = 0 ; j < 5 ; j++) ans = min(ans , dis[x][y][j]);
	cout<<ans<<'\n';
	return 0;
}

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