Submission #1199450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199450		Saul0906	Soccer (JOI17_soccer)	C++20	35 / 100	1370 ms	33684 KiB

soccer

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define repa(a,b) for(auto a:b)
#define mid ((l+r)>>1)
#define endl "\n"
#define pq_min(a) priority_queue<a,vector<a>,greater<a>>
#define lll array<ll,3>
#define pb push_back
#define ppb pop_back

using namespace std;

using vi = vector<int>;

const ll inf=1e18;
const int mov[4][2]{
	{1,0},
	{0,1},
	{-1,0},
	{0,-1}
};

inline ll abss(ll a){
	if(a>=0) return a;
	return -a;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll h, w, a, b, c, n;
	cin>>h>>w>>a>>b>>c>>n;
	h++;
	w++;
	int s[n], t[n];
	ll dis[h+2][w+2], vis[h+2][w+2]{}, cr[h+1][w+1], cc[h+1][w+1];
	rep(i,0,n){
		cin>>s[i]>>t[i];
		s[i]++;
		t[i]++;
		vis[s[i]][t[i]]=true;
	}
	rep(i,1,h+1) rep(j,1,w+1) cc[i][j]=cr[i][j]=inf;
	rep(i,1,h+1){
		ll mn=inf;
		rep(j,1,w+1){
			if(vis[i][j]) mn=0;
			cc[i][j]=min(cc[i][j],mn);
			mn++;
		}
		mn=inf;
		repr(j,w+1,1){
			if(vis[i][j]) mn=0;
			cc[i][j]=min(cc[i][j],mn);
			mn++;
		}
	}
	rep(j,1,w+1){
		ll mn=inf;
		rep(i,1,h+1){
			if(vis[i][j]) mn=0;
			cr[i][j]=min(cr[i][j],mn);
			mn++;
		}
		mn=inf;
		repr(i,h+1,1){
			if(vis[i][j]) mn=0;
			cr[i][j]=min(cr[i][j],mn);
			mn++;
		}
	}
	rep(i,0,h+2) rep(j,0,w+2) vis[i][j]=1;
	rep(i,1,h+1) rep(j,1,w+1) vis[i][j]=0;
	rep(i,0,h+2) rep(j,0,w+2) dis[i][j]=inf;
	pq_min(lll) pq;
	pq.push({0,s[0],t[0]});
	dis[s[0]][t[0]]=0;
	while(pq.size()){
		ll x=pq.top()[1], y=pq.top()[2], W=pq.top()[0], z;
		pq.pop();
		if(vis[x][y]) continue;
		vis[x][y]=true;
		rep(i,0,4){
			x+=mov[i][0];
			y+=mov[i][1];
			if(!vis[x][y] && dis[x][y]>W+c){
				dis[x][y]=W+c;
				pq.push({dis[x][y],x,y});
			}
			x-=mov[i][0];
			y-=mov[i][1];
		}
		if(a<c){
			rep(i,1,h+1){
				if(cc[i][y]<inf) z=min(inf,W+a*abss(x-i)+b+c*cc[i][y]);
				else z=inf;
				if(!vis[i][y] && dis[i][y]>z){
					dis[i][y]=z;
					pq.push({z,i,y});
				}
			}
			rep(i,1,w+1){
				if(cr[x][i]<inf) z=min(inf,W+a*abss(y-i)+b+c*cr[x][i]);
				else z=inf;
				if(!vis[x][i] && dis[x][i]>z){
					dis[x][i]=z;
					pq.push({z,x,i});
				}
			}
		}
	}
	cout<<dis[s[n-1]][t[n-1]]<<endl;
}

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