Submission #334914

#	Time	Username	Problem	Language	Result	Execution time	Memory
334914		YJU	Soccer (JOI17_soccer)	C++14	100 / 100	659 ms	20064 KiB

soccer

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
typedef pair<ll,pair<int,pll> > plll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=5e2+5;
const ll K=350;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

queue<pll> q;
ll cost[N][N],dis[5][N][N],d;
int n,a,b,c;
int H,W,sx,sy,ex,ey,x,y,ty;
int dx[5]={0,-1,0,0,1},dy[5]={0,0,-1,1,0};
priority_queue<plll,vector<plll>,greater<plll> > pq;

bool ck(short nx,short ny){
	return (nx>=0&&nx<=H&&ny>=0&&ny<=W);
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>H>>W;
	cin>>a>>b>>c;
	cin>>n;
	memset(dis,-1,sizeof(dis));
	REP1(i,n)cin>>x>>y,q.push(mp(x,y)),cost[x][y]=0,dis[0][x][y]=INF,sx=(i==1?x:sx),sy=(i==1?y:sy);
	ex=x;ey=y;
	while(SZ(q)){
		x=q.front().X;y=q.front().Y;q.pop();
		REP1(i,4){
			if(ck(x+dx[i],y+dy[i])&&dis[0][x+dx[i]][y+dy[i]]==-1){
				dis[0][x+dx[i]][y+dy[i]]=INF;
				cost[x+dx[i]][y+dy[i]]=cost[x][y]+c;
				q.push(mp(x+dx[i],y+dy[i]));
			}
		}
	}
	
	REP(ii,5)REP(i,H+1)REP(j,W+1)dis[ii][i][j]=INF;
	
	pq.push(mp(dis[0][sx][sy]=0,mp(0,mp(sx,sy))));
	while(SZ(pq)){
		d=pq.top().X,ty=pq.top().Y.X,x=pq.top().Y.Y.X,y=pq.top().Y.Y.Y;pq.pop();
		if(dis[ty][x][y]!=d)continue;
		if(ty==0){
			REP1(i,4){
				ll nx=x+dx[i],ny=y+dy[i];
				if(ck(nx,ny)&&dis[ty][nx][ny]>d+c){
					pq.push(mp(dis[ty][nx][ny]=d+c,mp(ty,mp(nx,ny))));
				}
				if(ck(nx,ny)&&dis[i][nx][ny]>d+b+a){
					pq.push(mp(dis[i][nx][ny]=d+b+a,mp(i,mp(nx,ny))));
				}
			}
		}else{
			if(dis[0][x][y]>d+cost[x][y])pq.push(mp(dis[0][x][y]=d+cost[x][y],mp(0,mp(x,y))));
			ll nx=x+dx[ty],ny=y+dy[ty];
			if(ck(nx,ny)&&dis[ty][nx][ny]>d+a)pq.push(mp(dis[ty][nx][ny]=d+a,mp(ty,mp(nx,ny))));
		}
	}
	cout<<dis[0][ex][ey]<<"\n";
	return 0;
}

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