RE求调
查看原帖
RE求调
774677
iakioi114514楼主2024/4/17 21:50

RERE #2 #3 #4 #5 #6 #7 #8 #9 #10。

#include<bits/stdc++.h>
using namespace std;
struct Edge{
	long long to,nxt,w;
}edge[1000010];
long long head[1000010],edge_num=0;
void add_edge(long long from,long long to,long long w){
	edge_num++;
	edge[edge_num].to=to;
	edge[edge_num].w=w;
	edge[edge_num].nxt=head[from];
	head[from]=edge_num;
}
long long x,y,z,vis[1000010],dis[1000010],ans;
unsigned long long h;
queue<long long> q;
bool SPFA(){
	vis[1]=1;
	dis[1]=1;
	q.push(1);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].w){
				dis[v]=dis[u]+edge[i].w;
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
}
int main(){
	memset(dis,0x3f,sizeof(dis));
	cin>>h>>x>>y>>z;
	if(x==1||y==1||z==1){
		cout<<h<<endl;
		return 0;
	}
	for(int i=0;i<x;i++){
		add_edge(i,(i+y)%x,y);
		add_edge(i,(i+z)%x,z);
	}
	SPFA();
	for(int i=0;i<x;i++){
		if(dis[i]<=h) ans=ans+(h-dis[i])/x+1;
	}
	cout<<ans<<endl;
	return 0;
}
2024/4/17 21:50
加载中...