G. Moving Platforms
There is a game where you need to move through a labyrinth. The labyrinth consists of $n$ platforms, connected by $m$ passages.
Each platform is at some level $l_i$, an integer number from $0$ to $H - 1$. In a single step, if you are currently on platform $i$, you can stay on it, or move to another platform $j$. To move to platform $j$ they have to be connected by the passage, and their levels have to be the same, namely $l_i = l_j$.
After each step, the levels of all platforms change. The new level of platform $i$ is calculated as $l'_i = (l_i + s_i) \bmod H$, for all $i$.
You start on platform $1$. Find the minimum number of steps you need to get to platform $n$.
Input
The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then the descriptions of the test cases follow.
The first line of each test case contains three integers $n$, $m$, and $H$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$, $1 \le H \le 10^9$).
The second line contains $n$ integers $l_i$, the initial level of each platform ($0 \le l_i \le H-1$).
The third line contains $n$ integers $s_i$, the change of level for each platform ($0 \le s_i \le H-1$).
Next $m$ lines contain a description of the passages. Each passage is described as a pair of integers — the platforms, connected by the passage. There is at most one passage connecting each pair of platforms, and there is no passage connecting a platform to itself.
The sum of $n$ for all tests does not exceed $10^5$, the sum of $m$ for all tests does not exceed $10^5$.
Output
For each test case, print a single integer, the minimum number of steps needed to get from platform $1$ to platform $n$.
If it is impossible to get to platform $n$, print $-1$.
Example
input
3
3 3 10
1 9 4
2 3 0
1 2
3 2
1 3
2 1 10
1 2
4 6
1 2
8 7 25
22 14 5 3 10 14 11 1
9 5 4 10 7 16 18 18
2 8
6 3
3 5
7 5
2 6
1 4
4 7
output
6
-1
52
Note
This is how levels of the platforms change, and what actions we need to perform in the first example.
Platform 1 | Platform 2 | Platform 3 | Action | |
Step 1 | 1 | 9 | 4 | Stay on the platform 1 |
Step 2 | 3 | 2 | 4 | Stay on the platform 1 |
Step 3 | 5 | 5 | 4 | Move to the platform 2 |
Step 4 | 7 | 8 | 4 | Stay on the platform 2 |
Step 5 | 9 | 1 | 4 | Stay on the platform 2 |
Step 6 | 1 | 4 | 4 | Move to the platform 3 |
解题思路
前置知识:扩展欧几里得算法用于求解 $ax+by=\gcd(a,b)$ 的可行解。对于任意方程 $ax+by=m$ 存在可行解的充要条件是 $\gcd(a,b) \mid m$,如果有解则先通过 exgcd 求出 $ax+by=\gcd(a,b)$ 的一组可行解 $x_0'$ 和 $y_0'$,那么 $x_0 = \frac{m}{\gcd(a,b)} \cdot x_0'$ 与 $y_0 = \frac{m}{\gcd(a,b)} \cdot y_0'$ 就是 $ax+by=m$ 的一组可行解。得到可行解后就可以构造通解 $\displaylines{\begin{cases} x = x_0 + k \cdot \frac{b}{\gcd(a,b)} \\ y = y_0 - k \cdot \frac{a}{\gcd(a,b)} \end{cases}}$,其中 $k \in \mathbb{Z}$。
相邻两点 $u$ 和 $v$ 只有在高度相同时的时刻才能从 $u$ 走到 $v$,假设到达 $u$ 的时刻为 $\text{dist}_u$,现在要求满足 $l_u + s_u x \equiv l_v + s_v x \pmod{H}$ 且大于等于 $\text{dist}_u$ 的最小时刻 $x$。该同余方程等价于 $(s_u - s_v) x + H y = l_v - l_u, \, y \in \mathbb{Z}$,$s_u - s_v$ 相当于 $a$,$H$ 相当于 $b$,$l_v - l_u$ 相当于 $m$。为了方便如果 $a < 0$,则令 $a \gets (a \bmod H + H) \bmod H$,即把 $a$ 变成模 $H$ 意义下最小的非负整数,同余方程仍然成立,同理 $b$ 和 $m$。
令 $d = \gcd(s_u - s_v, H)$,先求出 $(s_u - s_v) x + H y = d$ 的可行解 $x_0'$,那么 $x_0 = \frac{l_v - l_u}{d} \cdot x_0'$ 就是 $(s_u - s_v) x + H y = l_v - l_u$ 的可行解,令 $z = \frac{k}{d}$,那么 $x = x_0 + k z$ 就是通解。接着求满足 $x \geq \text{dist}_u$ 的最小 $x$,如果 $x_0 = \text{dist}_u$ 那么直接有 $x = x_0$。否则如果 $x_0 > \text{dist}_u$,那么需要 $x_0 - k z \geq \text{dist}_u, \, k \geq 0$,等价于 $k \leq \left\lfloor\frac{x_0 - \text{dist}_u}{z}\right\rfloor$,$k$ 取等号即可,则 $x = x_0 + \left\lfloor\frac{x_0 - \text{dist}_u}{z}\right\rfloor \cdot z$。同理如果 $x_0 < \text{dist}_u$,那么需要 $x_0 + k z \geq \text{dist}_u, \, k \geq 0$,等价于 $k \leq \left\lceil\frac{\text{dist}_u - x_0}{z}\right\rceil$,$k$ 取等号,则 $x = x_0 + \left\lceil\frac{\text{dist}_u - x_0}{z}\right\rceil \cdot z$。
以上就是求每个相邻节点边权的做法,然后就可以用 Dijkstra 跑最短路了。简单证明一下正确性,假设当前未标记的节点中 $\text{dist}_u$ 最小,那么不可能再通过其他未标记的节点 $v$ 来更新使得 $\text{dist}_u$ 变小,因为 $\text{dist_v} \geq \text{dist_u}$ 而从 $v$ 到 $u$ 的最小时刻 $x \geq \text{dist}_v$,所以与一般的 Dijkstra 一样标记 $u$ 并更新其他未标记节点的最小值即可。
AC 代码如下,时间复杂度为 $O(m \log{H} + m \log{m})$:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = N * 2;
int h[N], e[M], ne[M], idx;
int a[N], b[N];
LL dist[N];
bool vis[N];
void add(int u, int v) {
e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
void solve() {
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
}
for (int i = 1; i <= n; i++) {
scanf("%d", b + i);
}
memset(h, -1, n + 10 << 2);
idx = 0;
while (m--) {
int u, v;
scanf("%d %d", &u, &v);
add(u, v), add(v, u);
}
priority_queue<array<LL, 2>> pq;
pq.push({0, 1});
memset(dist, 0x3f, n + 10 << 3);
dist[1] = 0;
memset(vis, 0, n + 10);
while (!pq.empty()) {
auto p = pq.top();
pq.pop();
if (vis[p[1]]) continue;
vis[p[1]] = true;
for (int i = h[p[1]]; i != -1; i = ne[i]) {
int x, y;
int d = exgcd((b[p[1]] - b[e[i]] + k) % k, k, x, y);
if ((a[e[i]] - a[p[1]]) % d) continue;
LL t = LL(a[e[i]] - a[p[1]] + k) % k / d * x;
LL z = k / d;
if (t > -p[0]) t -= (t + p[0]) / z * z;
else if (t < -p[0]) t += (-p[0] - t + z - 1) / z * z;
if (dist[e[i]] > t + 1) {
dist[e[i]] = t + 1;
pq.push({-t - 1, e[i]});
}
}
}
printf("%lld\n", dist[n] == 0x3f3f3f3f3f3f3f3f ? -1 : dist[n]);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}
参考资料
Codeforces Round 927 (Div. 3) A-G:https://zhuanlan.zhihu.com/p/682734505
标签:10,le,dist,platform,int,text,Platforms,Moving From: https://www.cnblogs.com/onlyblues/p/18022870