제출 #1321663

#제출 시각아이디문제언어결과실행 시간메모리
1321663exoworldgdSoccer (JOI17_soccer)C++20
100 / 100
1139 ms20668 KiB
#include<bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
#define int long long
using namespace std;
const int INF=1e18,MX=600;
int h,w,a,b,c,n,pref[505][505],dp[505][505],g1[505],g2[505],s[100005][2];
signed main(void){
	exoworldgd;
	cin>>h>>w>>a>>b>>c>>n,h++,w++;
	for(int i=0;i<h;i++)for(int j=0;j<w;j++)pref[i][j]=INF;
	for(int i=0;i<n;i++)cin>>s[i][0]>>s[i][1],pref[s[i][0]][s[i][1]]=0;
	if(c<=a){cout<<(abs(s[0][0]-s[n-1][0])+abs(s[0][1]-s[n-1][1]))*c;return 0;}
	set<array<int,2>>st;
	for(int i=0;i<n;i++)st.insert({0,s[i][0]*w+s[i][1]});
	for(int i,j;st.size();){
		i=st.begin()->at(1)/w,j=st.begin()->at(1)%w,st.erase(st.begin());
		for(int ij=max(0LL,j-1);ij<min(j+2,w);ij++)if(pref[i][ij]>pref[i][j]+abs(ij-j)*c)st.erase({pref[i][ij],i*w+ij}),pref[i][ij]=pref[i][j]+abs(ij-j)*c,st.insert({pref[i][ij],i*w+ij});
		for(int ij=max(0LL,i-1);ij<min(i+2,h);ij++)if(pref[ij][j]>pref[i][j]+abs(ij-i)*c)st.erase({pref[ij][j],ij*w+j}),pref[ij][j]=pref[i][j]+abs(i-ij)*c,st.insert({pref[ij][j],ij*w+j});
	}
	for(int i=0;i<h;i++)for(int j=0;j<w;j++)dp[i][j]=INF;
	dp[s[0][0]][s[0][1]]=0,st.insert({0,s[0][0]*w+s[0][1]});
	while(st.size()){
		int i=st.begin()->at(1)/w,j=st.begin()->at(1)%w;
		if(dp[s[n-1][0]][s[n-1][1]]<=c+st.begin()->at(0)&&dp[s[n-1][0]][s[n-1][1]]<=a+b+st.begin()->at(0)){cout<<dp[s[n-1][0]][s[n-1][1]];return 0;}
		st.erase(st.begin());
		if(g1[i]<MX){
			g1[i]++;
			for(int ij=0;ij<w;ij++)if(dp[i][ij]>dp[i][j]+abs(ij-j)*a+b+pref[i][ij])st.erase({dp[i][ij],i*w+ij}),dp[i][ij]=dp[i][j]+abs(ij-j)*a+b+pref[i][ij],st.insert({dp[i][ij],i*w+ij});
		}
		if(g2[j]<MX){
			g2[j]++;
			for(int ij=0;ij<h;ij++)if(dp[ij][j]>dp[i][j]+abs(ij-i)*a+b+pref[ij][j])st.erase({dp[ij][j],ij*w+j}),dp[ij][j]=dp[i][j]+abs(i-ij)*a+b+pref[ij][j],st.insert({dp[ij][j],ij*w+j});
		}
		for(int ij=max(0LL,j-1);ij<min(j+2,w);ij++)if(dp[i][ij]>dp[i][j]+abs(ij-j)*c)st.erase({dp[i][ij],i*w+ij}),dp[i][ij]=dp[i][j]+abs(ij-j)*c,st.insert({dp[i][ij],i*w+ij});
		for(int ij=max(0LL,i-1);ij<min(i+2,h);ij++)if(dp[ij][j]>dp[i][j]+abs(ij-i)*c)st.erase({dp[ij][j],ij*w+j}),dp[ij][j]=dp[i][j]+abs(i-ij)*c,st.insert({dp[ij][j],ij*w+j});
	}
	cout<<dp[s[n-1][0]][s[n-1][1]];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...