1 条题解
-
0
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 100000; int h, x, y, z; vector<pair<int, int>> e[MAXN + 5]; int dis[MAXN + 5]; bool vis[MAXN + 5]; priority_queue<pair<int, int>> pq; signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> h >> x >> y >> z; h--; for (int i = 0; i <= x - 1; i++) { e[i].push_back({(i + y) % x, y}); e[i].push_back({(i + z) % x, z}); } for (int i = 0; i <= x - 1; i++) { dis[i] = h + 1; vis[i] = false; } dis[0] = 0; pq.push({-0, 0}); while (!pq.empty()) { int u = pq.top().second; pq.pop(); if (vis[u]) continue; vis[u] = true; for (int i = 0; i < e[u].size(); i++) { int v = e[u][i].first; int w = e[u][i].second; if (dis[u] + w < dis[v]) { dis[v] = dis[u] + w; pq.push({-dis[v], v}); } } } int ans = 0; for (int i = 0; i <= x - 1; i++) { if (dis[i] > h) continue; ans += (h - dis[i]) / x + 1; } cout << ans; return 0; }
- 1
信息
- ID
- 3980
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 5
- 标签
- 递交数
- 22
- 已通过
- 12
- 上传者