奇怪的90分。。不是因为没特判。。。
  • 板块P3403 跳楼机
  • 楼主shitbro
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/6/12 18:59
  • 上次更新2023/11/4 21:58:14
查看原帖
奇怪的90分。。不是因为没特判。。。
90972
shitbro楼主2021/6/12 18:59
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

const int N = 1e5 + 5;

struct edge {
	int to,val;
};
vector <edge> V[N];
long long h;
int x,y,z; 
long long d[N];
bool vis[N];

void add (int u,int v,int w) {
	V[u].push_back ((edge){v,w});
}
void dij () {
	priority_queue <pair <int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
	q.push (make_pair (1,1));
	for (int i = 0;i < x;i ++) d[i] = -1ull >> 1;
	d[1 % x] = 1;
	while (!q.empty ()) {
		int u = q.top().second;
		q.pop ();
		if(vis[u]) continue;
		vis[u] = 1;
		for (int i = 0;i < V[u].size ();i ++) {
			int v = V[u][i].to;
			if (d[u] + V[u][i].val < d[v]) {
				d[v] = d[u] + V[u][i].val;
				q.push (make_pair (d[v],v));
			}
		}
	}
}
int main(){
	cin >> h;
	cin >> x >> y >> z;
	for (int i = 0;i < x;i ++) {
		add (i,(i + y) % x,y);
		add (i,(i + z) % x,z);
	}
	dij ();
	long long res = 0;
	for (int i = 0;i < x;i ++) {
		if (d[i] <= h) res += (h - d[i]) / x + 1;
	}
	cout << res << endl;
	return 0;
}
2021/6/12 18:59
加载中...