P3403 跳楼机

P3403 跳楼机

同余最短路经典例题。

取一种移动方式为向上移动 k 层。不难想到，研究大于等于 k 的楼层没有意义，因为它们都可以从更小的楼层向上。记 d[x] 为通过该方式以外的能够到达的在膜 k 意义 x 的剩余系中的最低层数，那么 d[x] d[x] + k d[x] + 2k 均可以到达，共 (h - d[x]) / k + 1 种。因为按照不同的剩余系统计答案，所以不重不漏，答案即为 $\displaystyle \sum _ i ^ {k - 1} \left \lfloor \frac {h - d[i]} k \right \rfloor + 1$ 。现在考虑怎么计算答案。对于每一个小于 k 的楼层 i ，对于每一种上升的方式 x ，add(i, (i + x) % k, x) ，求最短路即可。

查看代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <climits>
#define INF LLONG_MAX
using namespace std;
const int N = 1e5 + 10, M = N << 1;
long long h, x, y, z, ans, dis[N];
bool vis[N];
int idx, hd[N], nxt[M], edg[M], wt[M];

void add(int x, int y, int z)
{
    nxt[++idx] = hd[x];
    hd[x] = idx;
    edg[idx] = y;
    wt[idx] = z;
}
void spfa()
{
    for (int i = 0; i < x; i++)
        dis[i] = INF;
    queue<int> q;
    q.push(0);
    vis[0] = true;
    dis[0] = 1;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        vis[x] = false;
        for (int i = hd[x]; i; i = nxt[i])
        {
            int y = edg[i];
            if (dis[y] > dis[x] + wt[i])
            {
                dis[y] = dis[x] + wt[i];
                if (!vis[y])
                {
                    q.push(y);
                    vis[y] = true;
                }
            }
        }
    }
}

int main()
{
    cin >> h >> x >> y >> z;
    for (int i = 0; i < x; i++)
    {
        add(i, (i + y) % x, y);
        add(i, (i + z) % x, z);
    }
    spfa();
    for (int i = 0; i < x; i++)
        if (dis[i] <= h)
            ans += (h - dis[i]) / x + 1;
    cout << ans;
    return 0;
}