Submission #854821

#	Time	Username	Problem	Language	Result	Execution time	Memory
854821		willychan	Soccer (JOI17_soccer)	C++14	0 / 100	11 ms	12376 KiB

soccer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
const int N = 126000;
vector<pair<int,int> > side[N];
ll dis[505][505];
ll ans[N];
int H,W;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
vector<pair<int,int> > loc;
int a,b,c;
bool inbound(int x,int y){
	return (x>=1 && x<=H && y>=1 && y<=W);
}
bool inbound2(int x,int y){
	return (x>=0 && x<=H && y>=0 && y<=W);
}

int mp(int x,int y,int l){
	return ((W+1)*(x)+y)+(((H+1)*(W+1))*l);
}

void get_dis(){
	for(int i=0;i<=H;i++){
		for(int j=0;j<=W;j++) dis[i][j]=1e15;
	}
	queue<pair<int,int> > q;
	for(auto i :loc){
		dis[i.first][i.second]=0;
		q.push(i);
	}
	while(q.size()){
		pair<int,int> cur = q.front();
		q.pop();
		for(int i=0;i<4;i++){
			int x = cur.first+dx[i];
			int y = cur.second+dy[i];
			if(!inbound2(x,y)) continue;
			if(dis[x][y]<1e15) continue;
			dis[x][y] = dis[cur.first][cur.second]+c;
			q.push({x,y});
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>H>>W;		
	cin>>a>>b>>c;
	int n;cin>>n;
	for(int i=0;i<n;i++){
		pair<int,int> f;
		cin>>f.first>>f.second;
		loc.push_back(f);
	}
	get_dis();
	for(int i=0;i<=H;i++){
		for(int j=0;j<=W;j++){
			//cout<<"s"<<mp(i,j,0);
			for(int k=0;k<4;k++){
			//	cout<<","<<mp(i,j,k+1);
				if(inbound2(i+dx[k],j+dy[k])){
					side[mp(i,j,k+1)].push_back({mp(i+dx[k],j+dy[k],k+1),a});
					side[mp(i,j,0)].push_back({mp(i+dx[k],j+dy[k],0),c});
				}
				side[mp(i,j,k+1)].push_back({mp(i,j,0),0});
				side[mp(i,j,0)].push_back({mp(i,j,k+1),dis[i][j]+b});
			}
		}
	}
	for(int i=0;i<N;i++) ans[i] = 1e18;
	ans[mp(loc[0].first,loc[0].second,0)]=0;
	priority_queue<pair<ll,int> ,vector<pair<ll,int> >,greater<pair<ll,int> > > pq;
	pq.push({0,mp(loc[0].first,loc[0].second,0)});
	while(pq.size()){
		pair<ll,int> cur=  pq.top()	;
		pq.pop();
		if(cur.first!=ans[cur.second]) continue;
		for(auto e : side[cur.second]){
			if(ans[e.first]>ans[cur.second]+e.second){
				ans[e.first] =ans[cur.second]+e.second;
				pq.push({ans[e.first],e.first});
			}
		}
	}
	cout<<ans[mp(loc[n-1].first,loc[n-1].second,0)]<<"\n";
	return 0;
}

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