Submission #377005

#	Time	Username	Problem	Language	Result	Execution time	Memory
377005		astoria	Soccer (JOI17_soccer)	C++14	35 / 100	571 ms	35040 KiB

soccer

#include "bits/stdc++.h"
using namespace std;

#define int long long

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int h,w,a,b,c,n;
	cin>>h>>w>>a>>b>>c>>n;
	
	int s[n],t[n];
	for(int i=0; i<n; i++) cin>>s[i]>>t[i];
	
	vector<pair<int,int> > adj[n];
	
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			int difs = abs(s[i]-s[j]);
			int dift = abs(t[i]-t[j]);
			
			int optOne = (a*difs) + b + (c*dift);
			if(difs==0) optOne-=b;
			int optTwo = (a*dift) + b + (c*difs);
			if(dift==0) optTwo-=b;
			int optThree = (c*difs) + (c*dift);
			
			int dist = min(min(optOne,optTwo),optThree);
			adj[i].push_back({j,dist});
			adj[j].push_back({i,dist});
		}
	}
	
	int dist[n];
	memset(dist,-1,sizeof(dist));
	dist[0] = 0;
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
	pq.push({0,0});
	while(!pq.empty()){
		int v = pq.top().first, di = pq.top().second; pq.pop();
		if(dist[v] != di) continue;
		for(auto ii : adj[v]){
			int nv = ii.first, nd = ii.second+di;
			if(dist[nv] != -1 && dist[nv] <= nd) continue;
			dist[nv] = nd;
			pq.push({nv,nd});
		}
	}
	cout<<dist[n-1];
	
}

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