求Hack
查看原帖
求Hack
923953
mahaorui2012楼主2025/1/20 10:47

为什么我的做法是错的?

40pts 1,3,6,8AC

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

long long dis[100005];
struct edge{
	int v,w;
};vector<edge> g[100005];

struct state{
	int u,dis;
};

const bool operator<(const state& a,const state& b){
	return !(a.dis<b.dis);
}

int main(){
	memset(dis,0x3f3f,sizeof(dis));
	long long h;
	cin>>h;
	int x,y,z;
	cin>>x>>y>>z;
	if(x==1 || y==1 || z==1){
	    cout<<h;
	    return 0;
	}
	for(int i=0;i<x;++i){
		g[i].push_back({(i+y)%x,(i+y)/x});
		//cout<<i<<' '<<i+y<<' '<<(i+y)%x<<' '<<(i+y)/x<<endl;
		g[i].push_back({(i+z)%x,(i+z)/x});
		//cout<<i<<' '<<i+z<<' '<<(i+z)%x<<' '<<(i+z)/x<<endl;
	}dis[0]=0;
	priority_queue<state> pq;
	pq.push({0,0});
	while(!pq.empty()){
		state top=pq.top();
		pq.pop();
		for(auto p:g[top.u]){
			if(dis[top.u]+p.w<dis[p.v]){
				dis[p.v]=dis[top.u]+p.w;
				pq.push({p.v,dis[p.v]});
			}
		}
	}long long _h=h;
	for(int i=0;i<x;++i){
		h-=min(dis[i],(_h-i-1)/x);
		//cout<<dis[i]<<' '<<(_h-i)/x<<endl;
	}cout<<h;
	return 0;
}
2025/1/20 10:47
加载中...