제출 #1199444

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199444		Saul0906	Soccer (JOI17_soccer)	C++20	35 / 100	1480 ms	327680 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 pair<ll,pll>
#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}
};

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], col[w]{}, row[h]{};
	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){
		cc[i][0]=inf;
		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){
		cr[0][j]=inf;
		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().se.fi, y=pq.top().se.se, W=pq.top().fi, 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];
		}
		rep(i,1,h+1){
			if(cc[i][y]<inf) z=W+a*abs(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=W+a*abs(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}});
			}
		}
		row[x]=true;
		col[y]=true;
	}
	cout<<dis[s[n-1]][t[n-1]]<<endl;
}

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