Submission #1279232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279232		PieArmy	Soccer (JOI17_soccer)	C++20	100 / 100	400 ms	21984 KiB

soccer

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
#define int ll

const int inf=5e15;
int n,m,k;
int a,b,c;
pair<int,int>bas,tar;
int table[523][523];
int dp[523][523][5];

int32_t main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n>>m>>a>>b>>c>>k;
	{
		priority_queue<pair<int,pair<int,int>>>pq;
		for(int i=0;i<=n;i++){
			for(int j=0;j<=m;j++){
				table[i][j]=inf;
				for(int l=0;l<5;l++){
					dp[i][j][l]=inf;
				}
			}
		}
		for(int i=1;i<=k;i++){
			pair<int,int>p;cin>>p.fr>>p.sc;
			if(i==1)bas=p;
			if(i==k)tar=p;
			if(!table[p.fr][p.sc])continue;
			table[p.fr][p.sc]=0;
			pq.push({0,{p.fr,p.sc}});
		}
		while(pq.size()){
			int dis=-pq.top().fr;
			int i=pq.top().sc.fr,j=pq.top().sc.sc;
			pq.pop();
			if(table[i][j]!=dis)continue;
			if(i){
				if(table[i-1][j]>table[i][j]+1){
					table[i-1][j]=table[i][j]+1;
					pq.push({-dis-1,{i-1,j}});
				}
			}
			if(j){
				if(table[i][j-1]>table[i][j]+1){
					table[i][j-1]=table[i][j]+1;
					pq.push({-dis-1,{i,j-1}});
				}
			}
			if(i!=n){
				if(table[i+1][j]>table[i][j]+1){
					table[i+1][j]=table[i][j]+1;
					pq.push({-dis-1,{i+1,j}});
				}
			}
			if(j!=m){
				if(table[i][j+1]>table[i][j]+1){
					table[i][j+1]=table[i][j]+1;
					pq.push({-dis-1,{i,j+1}});
				}
			}
		}
	}
	priority_queue<pair<int,pair<int,pair<int,int>>>>pq;
	dp[bas.fr][bas.sc][4]=0;
	pq.push({0,{4,bas}});

	function<void(int,int,int,int)>f=[&](int i,int j,int l,int cos)->void{
		if(i>n||j>m||i<0||j<0)return;
		if(dp[i][j][l]>cos){
			dp[i][j][l]=cos;
			pq.push({-cos,{l,{i,j}}});
		}
	};
	while(pq.size()){
		int dis=-pq.top().fr,tur=pq.top().sc.fr;
		int i=pq.top().sc.sc.fr,j=pq.top().sc.sc.sc;
		pq.pop();
		if(dp[i][j][tur]!=dis)continue;
		if(tur==4){
			f(i-1,j,4,dis+c);
			f(i+1,j,4,dis+c);
			f(i,j-1,4,dis+c);
			f(i,j+1,4,dis+c);

			f(i-1,j,0,dis+a+b);
			f(i+1,j,1,dis+a+b);
			f(i,j-1,2,dis+a+b);
			f(i,j+1,3,dis+a+b);
		}
		else{
			f(i,j,4,dis+table[i][j]*c);
			if(tur==0){
				f(i-1,j,0,dis+a);
			}
			if(tur==1){
				f(i+1,j,1,dis+a);
			}
			if(tur==2){
				f(i,j-1,2,dis+a);
			}
			if(tur==3){
				f(i,j+1,3,dis+a);
			}
		}
	}
	cout<<dp[tar.fr][tar.sc][4]<<endl;
}

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