Submission #334907

#	Time	Username	Problem	Language	Result	Execution time	Memory
334907		YJU	Soccer (JOI17_soccer)	C++14	35 / 100	2321 ms	262148 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<short,short> pll;
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[N][N],d;
int n,a,b,c,L;
short H,W,sx,sy,ex,ey,x,y;
int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
priority_queue<pair<ll,pll>,vector<pair<ll,pll> >,greater<pair<ll,pll> > > 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;
	if(a<c)L=b/(c-a);
	cin>>n;
	memset(dis,-1,sizeof(dis));
	REP1(i,n)cin>>x>>y,q.push(mp(x,y)),cost[x][y]=0,dis[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();
		REP(i,4){
			if(ck(x+dx[i],y+dy[i])&&dis[x+dx[i]][y+dy[i]]==-1){
				dis[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]));
			}
		}
	}
	pq.push(mp(dis[sx][sy]=0,mp(sx,sy)));
	while(SZ(pq)){
		d=pq.top().X,x=pq.top().Y.X,y=pq.top().Y.Y;pq.pop();
		if(d!=dis[x][y])continue;
		REP(i,4){
			int nx=x+dx[i],ny=y+dy[i];
			if(ck(nx,ny)&&dis[nx][ny]>d+c){pq.push(mp(dis[nx][ny]=d+c,mp(nx,ny)));}
			if(a<c){
				for(int j=L;;j++){
					nx=x+dx[i]*j,ny=y+dy[i]*j;
					if(!ck(nx,ny))break;
					if(dis[nx][ny]>d+b+a*j+cost[nx][ny]){
						pq.push(mp(dis[nx][ny]=d+b+a*j+cost[nx][ny],mp(nx,ny)));
					}
				}
			}
		}
	}
	cout<<dis[ex][ey]<<"\n";
	return 0;
}

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