3403,玄关,求调
  • 板块灌水区
  • 楼主apple_vinegar
  • 当前回复1
  • 已保存回复2
  • 发布时间2024/7/22 11:41
  • 上次更新2024/7/22 13:18:29
查看原帖
3403,玄关,求调
815957
apple_vinegar楼主2024/7/22 11:41
#include<bits/stdc++.h>
using namespace std;
const int N=2*1e5+5;
long long h1,ans;
long long w[N],e[N],h[N],ne[N],dis[N],f[N],idx,x,y,z;

void add(int a,int b,int c){
	e[idx]=b;
	w[idx]=c;
	ne[idx]=h[a];
	h[a]=idx++;
}

void dijkstra(){
	dis[0]=0;
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > heap;
	heap.push(make_pair(0,0));	
	while(!heap.empty()){
		long long x=heap.top().second;
		heap.pop();
		if(f[x]!=0) continue;
		f[x]=1;
		for(int i=h[x];i!=-1;i=ne[i]){
			int j=e[i];
			//cout<<ne[i]<<" "<<i<<" "<<j<<endl;
			if(dis[j]>w[i]+dis[x]){
				dis[j]=w[i]+dis[x];
				heap.push(make_pair(dis[j],j));
			}
		}
	}
}

int main(){
	memset(h,-1,sizeof h);
	cin>>h1;
	h1--;
	cin>>x>>y>>z;
	if(x>y) swap(x,y);
	if(x>z) swap(x,z);
	if(x==1){
		cout<<h1+1;
		return 0;
	}
	for(int i=0;i<x;i++){
		add(i,(i+y)%x,y);
		add(i,(i+z)%x,z);
		dis[i]=(1<<63)-1;
	}
	dijkstra();
	for(int i=0;i<x;i++){
		if(h1>=dis[i]){
			ans+=(h1-dis[i])/x+1;
		}
	}  
	cout<<ans;
	return 0;
} 
2024/7/22 11:41
加载中...