60pts求调
  • 板块P3403 跳楼机
  • 楼主hmwzd1314
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/2 18:07
  • 上次更新2024/8/2 19:27:35
查看原帖
60pts求调
735235
hmwzd1314楼主2024/8/2 18:07
#include<bits/stdc++.h>
#define int long long 
using namespace std;
int h,x,y,z,d[200009],ans;
bool vis[200009];
struct node
{
	int v,w;
};
vector<node>e[200009];
void sb()
{
	memset(d,0x3f3f3f3f,sizeof(d));
	priority_queue<pair<int,int> >q;
	q.push({0,0});
	d[0]=0;
	while(q.size())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=0;i<e[u].size();i++)
		{
			int v=e[u][i].v,w=e[u][i].w;
			if(d[u]+w<d[v])d[v]=d[u]+w,q.push({d[v],v});
		}
	}
}
signed main()
{
	cin>>h>>x>>y>>z;
	h--;
	if(x>y)swap(x,y);
	if(y>z)swap(y,z);
	if(x>y)swap(x,y);
	if(x==1)
	{
		cout<<h+1;
		return 0;
	}
	for(int i=0;i<x;i++)
	{
		e[i].push_back({(i+y)%x,y});
		e[i].push_back({(i+z)%x,z});
	}
	sb();
	for(int i=0;i<x;i++)if(d[i]<=h)ans+=(h-d[i])/x+1;
	cout<<ans;
	return 0;
}
2024/8/2 18:07
加载中...