제출 #824838

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
824838		kshitij_sodani	Soccer (JOI17_soccer)	C++17	100 / 100	479 ms	28908 KiB

soccer

#include <bits/stdc++.h>
#define a first
#define b second
#define pb push_back
using namespace std;
#define endl '\n'
typedef long long llo;


llo vis[501][501];
llo dist[501][501];
llo dp[501][501][6];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n,m;
	cin>>n>>m;
	llo aa,bb,cc;
	cin>>aa>>bb>>cc;
	llo nn;
	cin>>nn;
	vector<pair<llo,llo>> tt;
	for(llo i=0;i<nn;i++){
		llo ee,ff;
		cin>>ee>>ff;
		if(i<nn-1){
			vis[ee][ff]=1;
		}
		tt.pb({ee,ff});
	}
	queue<pair<llo,llo>> ss;
	for(llo i=0;i<=n;i++){
		for(llo j=0;j<=m;j++){
			if(vis[i][j]==1){
				dist[i][j]=0;
				ss.push({i,j});
			}
			else{
				dist[i][j]=-1;
			}
		}
	}
	vector<llo> x={-1,1,0,0};
	vector<llo> y={0,0,1,-1};

	while(ss.size()){
		pair<llo,llo> no=ss.front();
		ss.pop();
		for(llo j=0;j<4;j++){
			pair<llo,llo> rr={no.a+x[j],no.b+y[j]};
			if(rr.a<0 or rr.a>n or rr.b<0 or rr.b>m){
				continue;
			}
			if(dist[rr.a][rr.b]==-1){
				dist[rr.a][rr.b]=dist[no.a][no.b]+1;
				ss.push(rr);
			}
		}
	}

	for(llo i=0;i<=n;i++){
		for(llo j=0;j<=m;j++){
			//cout<<dist[i][j]<<",";
			for(llo kk=0;kk<6;kk++){
				dp[i][j][kk]=1e18;
			}
		}
		//cout<<endl;

	}
	dp[tt[0].a][tt[0].b][0]=0;
	priority_queue<pair<pair<llo,llo>,pair<llo,llo>>> qq;
	qq.push({{0,0},tt[0]});
	while(qq.size()){
		pair<pair<llo,llo>,pair<llo,llo>> no=qq.top();
		qq.pop();
		no.a.a=-no.a.a;
		if(dp[no.b.a][no.b.b][no.a.b]!=no.a.a){
			continue;
		}
		if(no.a.b==0){
			if(dp[no.b.a][no.b.b][1-no.a.b]>dp[no.b.a][no.b.b][no.a.b]+dist[no.b.a][no.b.b]*cc){
				dp[no.b.a][no.b.b][1-no.a.b]=dp[no.b.a][no.b.b][no.a.b]+dist[no.b.a][no.b.b]*cc;
				qq.push({{-dp[no.b.a][no.b.b][1],1},no.b});
			}
		}
		else if(no.a.b==1){
			for(llo j=0;j<4;j++){
				pair<llo,llo> rr={no.b.a+x[j],no.b.b+y[j]};
				if(rr.a<0 or rr.a>n or rr.b<0 or rr.b>m){
					continue;
				}
				if(dp[rr.a][rr.b][1]>dp[no.b.a][no.b.b][no.a.b]+cc){
					dp[rr.a][rr.b][1]=dp[no.b.a][no.b.b][no.a.b]+cc;
					qq.push({{-dp[rr.a][rr.b][1],1},rr});
				}
			}
			for(llo j=0;j<4;j++){
				pair<llo,llo> rr={no.b.a+x[j],no.b.b+y[j]};
				if(rr.a<0 or rr.a>n or rr.b<0 or rr.b>m){
					continue;
				}
				if(dp[rr.a][rr.b][j+2]>dp[no.b.a][no.b.b][no.a.b]+aa+bb){
					dp[rr.a][rr.b][j+2]=dp[no.b.a][no.b.b][no.a.b]+aa+bb;
					qq.push({{-dp[rr.a][rr.b][j+2],j+2},rr});
				}
			}
		}
		else{
			for(llo j=no.a.b-2;j<no.a.b-1;j++){
				pair<llo,llo> rr={no.b.a+x[j],no.b.b+y[j]};
				if(rr.a<0 or rr.a>n or rr.b<0 or rr.b>m){
					continue;
				}
				if(dp[rr.a][rr.b][no.a.b]>dp[no.b.a][no.b.b][no.a.b]+aa){
					dp[rr.a][rr.b][no.a.b]=dp[no.b.a][no.b.b][no.a.b]+aa;
					qq.push({{-dp[rr.a][rr.b][no.a.b],no.a.b},rr});
				}
			}
			if(dp[no.b.a][no.b.b][0]>dp[no.b.a][no.b.b][no.a.b]){
				dp[no.b.a][no.b.b][0]=dp[no.b.a][no.b.b][no.a.b];
				qq.push({{-dp[no.b.a][no.b.b][0],0},{no.b}});
			}
		}
	}
	llo ans=1e18;
/*	cout<<endl;

	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			cout<<dp[i][j][0]<<",";
		}
		cout<<endl;
	}*/
	for(llo i=0;i<6;i++){
		ans=min(ans,dp[tt.back().a][tt.back().b][i]);
	}
	cout<<ans<<endl;


	return 0;
}

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