数组越界求调
  • 板块P3403 跳楼机
  • 楼主jikky
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/29 21:12
  • 上次更新2024/10/30 08:53:22
查看原帖
数组越界求调
1382982
jikky楼主2024/10/29 21:12
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18+10;
const int N=1e6+10;

struct E{
	int ne;
	int v;
	int w;
}e[N<<4];
int tot=0;
int head[N];
int node[N];
struct NODE{
	int num;
	int id;
}dis[N];
void add(int u,int v,int w){
	e[++tot].ne=head[u];
	e[tot].v=v;
	e[tot].w=w;
	head[u]=tot;
}
struct cmp{
	bool operator ()(NODE a,NODE b){
		if(a.num>b.num){
			return 1;
		}
		else{
			return 0;
		}
	}
};
priority_queue<NODE,vector<NODE>,cmp> q;

int find(int u){
	q.pop();
	node[u]=1;
	for(int i=head[u];i!=inf;i=e[i].ne){
		if(dis[e[i].v].num>dis[u].num+e[i].w){
			dis[e[i].v].num=dis[u].num+e[i].w;
			q.push(dis[e[i].v]);
		}
	}
}

signed main(){
	long long h;
	int x,y,z;
	cin>>h>>x>>y>>z;
	h--;
	for(int i=0;i<x;i++){
		head[i]=inf;
	}
	for(int i=0;i<x;i++){
		add(i,(i+y)%x,y);
		add(i,(i+z)%x,z);
		dis[i].num=inf;
		dis[i].id=i;
	}
	dis[0].num=0;
	int ans=0;
	q.push(dis[0]);
	while(!q.empty()){
		if(!node[q.top().id]){
			find(q.top().id);
		}
		else{
			q.pop();
		}
	}
	for(int i=0;i<x;i++){
		if(dis[i].num!=inf){
			//cout<<i<<" ";
			ans+=((h-dis[i].num)/x+1);
		}
	}
	//cout<<endl;
	cout<<ans;
	return 0;
}
2024/10/29 21:12
加载中...