1 条题解

  • 0
    @ 2025-3-22 10:26:36
    #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
    上传者