Submission #1290479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290479		hackstar	Soccer (JOI17_soccer)	C++20	35 / 100	35 ms	18560 KiB

soccer

// #pragma GCC optimize("Ofast,O3,unroll-loops")
// #pragma GCC target("avx,avx2")
#include<bits/stdc++.h>
#include<random>
using namespace std;

#ifdef CM
#include "debug.h"
#else
#define debug(...) 42
#endif

#define pb emplace_back
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define aura 1e18
#define pii pair<int,int>
void die(string S){puts(S.c_str());exit(0);}
#define int long long
const int mod=1e9+7;
void solve()
{
	int h,w;
	cin>>h>>w;
	int a,b,c;
	cin>>a>>b>>c;
	int n;
	cin>>n;
	vector<pii>A(n);
	for(auto &[x,y]:A)
		cin>>x>>y;
	// srt(A);
	vector<vector<pii>>g(n);
	auto get=[&](int x,int y)->int
	{
		int x1=A[x].first,y1=A[x].second;
		int x2=A[y].first,y2=A[y].second;
		int ans=+aura;

		ans=min(ans,c*(abs(x1-x2)+abs(y1-y2)));
		ans=min(ans,(a*abs(y1-y2)+b) + c*abs(x1-x2));
		ans=min(ans,a*abs(x1-x2)+b + c*abs(y1-y2));

		return ans;
	};
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(j==i)
				continue;
			int w=get(i,j);
			g[i].pb(j,w);
		}
	}
	vector<int>dp(n,+aura);
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	pq.emplace(0,0);
	dp[0]=0;
	while(!pq.empty())
	{
		auto [d,u]=pq.top();
		pq.pop();
		if(d>dp[u])
			continue;
		for(auto [v,w]:g[u])
		{
			if(dp[u]+w<dp[v])
			{
				dp[v]=dp[u]+w;
				pq.emplace(dp[v],v);
			}
		}
	}
	cout<<dp[n-1]<<'\n';
}


signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	#ifdef CM
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	// cin>>t;
	while(t--)
		solve();
	return 0;
}

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