题目详细题解：G. Moving Platforms

问题重述

有 $n$ 个平台，每个平台 $i$ 有：

• 初始等级 $l_i$（$0 \le l_i < H$）
• 等级变化值 $s_i$（$0 \le s_i < H$）

时间 $t$ 时（$t$ 表示经过的步数），平台 $i$ 的等级为：

$$L_i(t) = (l_i + t \cdot s_i) \bmod H$$

每一步可以：

1. 停留在当前平台
2. 移动到相邻平台 $j$，前提是 $L_i(t) = L_j(t)$

目标：从平台 $1$ 到平台 $n$ 的最少步数。

---

核心观察

关键性质：两个平台是否在同一时刻具有相同等级，只取决于时间，与玩家之前的选择无关。

因此，最优策略是：一旦可以移动，就立即移动——贪心地尽早到达每个节点。这提示我们使用 Dijkstra 算法，其中“距离”就是到达该节点所需的最少步数。

---

问题转化：确定移动时机

假设在时刻 $t$ 我们位于节点 $v$，想通过边 $(v,u)$ 移动到 $u$。

我们需要找到最小的 $k \ge t$，使得：

$$L_v(k) = L_u(k)$$

即：

$$(l_v + k \cdot s_v) \bmod H = (l_u + k \cdot s_u) \bmod H $$

等价于：

$$l_v - l_u \equiv k \cdot (s_u - s_v) \pmod H$$

记：

$$a = (l_v - l_u) \bmod H \quad (\text{取 } 0 \le a < H) $$$$b = (s_u - s_v) \bmod H \quad (\text{取 } 0 \le b < H) $$

则方程变为：

$$a \equiv k \cdot b \pmod H \quad \text{且} \quad k \ge t $$

---

解线性同余方程

方程 $a \equiv k \cdot b \pmod H$ 等价于：

$$k \cdot b - a = H \cdot y \quad (y \in \mathbb{Z}) $$

即：

$$k \cdot b - H \cdot y = a$$

这是形如 $k \cdot b + H \cdot (-y) = a$ 的线性丢番图方程。

步骤 1：判断解的存在性

设 $g = \gcd(b, H)$。

根据数论，方程有解 当且仅当 $g \mid a$。

如果 $g \nmid a$，则永远无法从 $v$ 移动到 $u$（直接跳过这条边）。

步骤 2：简化方程

若 $g \mid a$，令：

$$b' = b/g, \quad H' = H/g, \quad a' = a/g$$

则原方程化为：

$$k \cdot b' \equiv a' \pmod{H'}$$

此时 $\gcd(b', H') = 1$，所以 $b'$ 在模 $H'$ 下可逆。

步骤 3：求解最小非负解

用扩展欧几里得算法求出 $b'$ 的模逆 $b'^{-1} \bmod H'$，则：

$$k_0 \equiv a' \cdot b'^{-1} \pmod{H'}$$

取 $k_0$ 为模 $H'$ 意义下的最小非负剩余。

步骤 4：找到 $\ge t$ 的最小解

所有解为：

$$k = k_0 + r \cdot H', \quad r \ge 0$$

我们要找最小的 $k \ge t$：

如果 $k_0 \ge t$，则 $k = k_0$。

否则，$k = k_0 + \left\lceil \frac{t - k_0}{H'} \right\rceil \cdot H'$。

记 $dt = k - t$，即需要等待的步数。

---

转移公式

当我们从 $v$ 出发（时刻 $t$），需要等待 $dt$ 步才能满足等级相等，然后再花 1 步 移动到 $u$。

所以到达 $u$ 的时刻为：

$$t' = t + dt + 1$$

其中 $dt$ 通过上述同余方程计算得出。

---

Dijkstra 算法框架

• 状态：节点编号 $v$，到达它的最短时间 $d[v]$（初始 $d[0] = 0$，其余 $\infty$）
• 优先队列按时间从小到大取出节点
• 对每个邻居 $u$：
  • 计算 $a, b, g$
  • 若 $a \bmod g \ne 0$，跳过
  • 求解最小 $k \ge d[v]$，满足同余式
  • 得到 $dt = k - d[v]$
  • 更新 $d[u] = \min(d[u], d[v] + dt + 1)$
• 最终答案：$d[n-1]$，若为 $\infty$ 则输出 $-1$

---

代码关键部分解析

// 扩展欧几里得，返回 (gcd, x, y) 满足 a*x + b*y = gcd
triple eucl(long a, long b) { ... }

// 在 Dijkstra 的松弛过程中
long a = (l[v] + (t % H) * s[v]) - (l[u] + (t % H) * s[u]);
a %= H; if (a < 0) a += H;
long b = s[u] - s[v];
b %= H; if (b < 0) b += H;

auto [dd, x, y] = eucl(b, H);  // dd = gcd(b, H)
if (a % dd != 0) continue;      // 无解

x *= a / dd;
x %= (H / dd);
if (x < 0) x += H / dd;         // x 就是 k0

long dt = x;
if (dt < d[v]) {                // 需要调整到 >= d[v]
    long step = H / dd;
    dt += ((d[v] - dt + step - 1) / step) * step;
}
long new_time = d[v] + dt + 1;

注意：代码中直接用 $x$ 作为 $k_0$，是因为方程化简后 $k_0 \equiv a' \cdot b'^{-1} \pmod{H'}$，且 $x$ 就是那个最小非负解。

---

复杂度分析

• 每个节点最多入队一次（Dijkstra）
• 每条边被松弛两次（无向图）
• 每次松弛计算一次扩展欧几里得：$O(\log H)$
• 总复杂度：$O((n + m) \log H + (n + m) \log n)$，可以通过 $n, m \le 10^5$ 的约束。

---

总结

这道题的核心难点在于：

1. 识别出“时间依赖的边权”可以通过解线性同余方程转化为静态图上的 Dijkstra。
2. 正确处理模运算，利用 $\gcd$ 化简方程。
3. 实现时注意 $H$ 可达 $10^9$，必须使用 $O(\log H)$ 的扩展欧几里得，不能暴力枚举。

通过上述方法，我们就能在合理的时间内求出从平台 $1$ 到平台 $n$ 的最少步数。

#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;
 
// @author: pashka
 
struct triple {
    long d, x, y;
};
 
triple eucl(long a, long b) {
    if (b == 0) {
        return {a, 1, 0};
    }
    long k = a / b;
    auto [d, x, y] = eucl(b, a - k * b);
    return {d, y, x - k * y};
}
 
struct test {
    void solve() {
        int n, m, H;
        cin >> n >> m >> H;
        vector<long> l(n);
        for (int i = 0; i < n; i++) cin >> l[i];
        vector<long> s(n);
        for (int i = 0; i < n; i++) cin >> s[i];
 
        vector<vector<int>> g(n);
        for (int i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            x--;
            y--;
            g[x].push_back(y);
            g[y].push_back(x);
        }
 
        const long INF = 1e18;
        vector<long> d(n, INF);
        d[0] = 0;
        set<pair<long, int>> q;
        q.insert({d[0], 0});
        while (!q.empty()) {
            auto p = *q.begin();
            q.erase(p);
            int v = p.second;
            long t = d[v];
            for (int u: g[v]) {
                long a = (l[v] + (t % H) * s[v]) - (l[u] + (t % H) * s[u]);
                a %= H;
                if (a < 0) a += H;
                long b = s[u] - s[v];
                b %= H;
                if (b < 0) b += H;
                // a - bx = yH
                auto [dd, x, y] = eucl(b, H);
                // xb + yH = dd
                if (a % dd != 0) continue;
                x *= a / dd;
                x %= (H / dd);
                if (x < 0) x += H / dd;
                long dt = x;
                if (d[v] + dt + 1 < d[u]) {
                    q.erase({d[u], u});
                    d[u] = d[v] + dt + 1;
                    q.insert({d[u], u});
                }
            }
        }
        long res = d[n - 1];
        if (res == INF) res = -1;
        cout << res << "\n";
    }
};
 
int main() {
    ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        test().solve();
    }
    
    return 0;
}