50pts 求调
  • 板块P3403 跳楼机
  • 楼主ztjp13
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/21 18:27
  • 上次更新2024/7/21 19:46:35
查看原帖
50pts 求调
342941
ztjp13楼主2024/7/21 18:27
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int maxn=100005;

int h,x,y,z;
int tot,ans;
int	head[maxn],edge[maxn],ver[maxn],Next[maxn]; 
int d[maxn],vis[maxn];

struct node{
	int id,step;
	bool operator <(const node b)const{
		return step>b.step;
	}
};

priority_queue<node>q;

inline int read(){
	int f=1,k=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		k=k*10+c-'0';
		c=getchar();
	}
	return f*k;
}

void add(int x,int y,int z){
	edge[++tot]=z; ver[tot]=y; Next[tot]=head[x]; head[x]=tot;
}

void dij(){
	d[0]=0;
	q.push(node{0,0});
	while(!q.empty()){
		int x=q.top().id; q.pop();
		if(vis[x]) continue;
		vis[x]=true;
		for(int i=head[x];i;i=Next[i]){
			int y=ver[i];
			int z=edge[i];
			if(d[y]>d[x]+z){
				d[y]=d[x]+z;
				q.push(node{y,d[y]});
			}
		}
	}
}

signed main(){
	h=read(); x=read(); y=read(); z=read();
	h--;
	for(int i=0;i<x;i++){
		add(i,(i+y)%x,y); 
		add(i,(i+z)%x,z); 
		d[i]=(1ull<<63)-1;
	}
	dij();
	for(int i=0;i<x;i++){
		if(h>=d[i]) ans+=(h-d[i])/x+1;
	}
	cout<<ans<<endl;
	return 0;
} 
2024/7/21 18:27
加载中...