SPFA求助 90pts WA on#10
  • 板块P3403 跳楼机
  • 楼主Guizy
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/1/18 08:20
  • 上次更新2024/1/18 08:59:40
查看原帖
SPFA求助 90pts WA on#10
604906
Guizy楼主2024/1/18 08:20
#include<bits/stdc++.h>
#define Max 200001
#define int long long
using namespace std;

int h,x,y,z;
int dis[Max],vis[Max];
struct node{
	int id,val;
};
struct Queue{
	int q[200001],l=0,r=0;
	void pop(){l++;}
	int size(){return r-l;}
	int front(){return q[l];}
	void push(int x){q[r++]=x;}
}que;
vector<node>G[Max];

void add(int u,int v,int w){
	G[u].push_back({v,w});
}

void spfa(){
	que.push(1),vis[1]=1;
	while(que.size()){
		int u=que.front();
		que.pop();
		for(auto v:G[u]){
			dis[v.id]=min(dis[v.id],dis[u]+v.val);
			if(!vis[v.id]){
				que.push(v.id),vis[v.id]=1;
			}
		}
	}

}

signed main(){
	
	scanf("%lld%lld%lld%lld",&h,&x,&y,&z);
	
	if(x==1||y==1||z==1){
		printf("%lld",h);
		return 0;
	}
	
	for(int i=0;i<x;i++){
		add(i,(i+z)%x,z);
		add(i,(i+y)%x,y);
	}
	
	for(int i=0;i<x;i++){
		dis[i]=1e27;
	}
	dis[1]=1,spfa();
	
	int ans=0;
	for(int i=0;i<x;i++){
		if(h>=dis[i])
			ans+=(h-dis[i])/x+1;
	}
	printf("%lld",ans);
}
2024/1/18 08:20
加载中...