首页 > 其他分享 >G. Moving Platforms

G. Moving Platforms

时间:2024-02-20 13:24:47浏览次数:26  
标签:10 le dist platform int text Platforms Moving

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

相关文章

  • CF1385F Removing Leaves 题解
    解题思路简单贪心,优先选择叶子节点最多的,这样能够保证一定能把所有能删的都删了。因为要建一个可删除的图,所以我们可以使用set来存边,不然就需要维护一堆东西……那么我们肯定是从有叶子节点的点向父亲更新的,那么我们每次选择叶子节点最多的点,然后删除\(k\)个叶子,判断一下删......
  • [ARC114D] Moving Pieces on Line 题解
    题目链接点击打开链接题目解法有点牛的题,前面的转化感觉很妙首先一个显然的性质是:一个棋子不可能走回头路,不然前面的路就白走了下面是最妙的一步:我们令\(st_i\)为\(i-1\toi\)和\(i\toi+1\)的颜色是否相同,那么问题可以转化成:选择\(\{p_i\}\),一开始所有点颜色为\(0\)......
  • CF351D Jeff and Removing Periods
    https://www.luogu.com.cn/problem/CF351D由于每次操作后存在重排操作,我们可以让序列(询问的区间)中的相同值放在一块,这样以后每次操作就能删掉一整个值相同的位置了。那么第二次操作后所需操作数就是当前序列中不同数的个数。经典数颜色问题,离线线段树/莫队/主席树都能做。数颜色......
  • Cisco Catalyst 8000 Series Edge Platforms, IOS XE Release Dublin-17.11.01a ED
    CiscoCatalyst8000SeriesEdgePlatforms,IOSXEReleaseDublin-17.11.01aEDCiscoCatalyst8000边缘平台系列作者主页:sysin.orgCiscoCatalyst8000:随心所欲访问位于云、数据中心和边缘的混合型应用和多云应用。特性和优势Catalyst8000边缘平台是一款基于意图的网络(IBN......
  • 无涯教程-批处理 - Moving Files函数
    对于移动文件,批处理脚本提供了MOVE命令。MOVE[/Y|/-Y][drive:][path]filename1[,...]destination以下是可以提供给DEL命令的选项的说明。S.No.Options&描述1.[drive:][path]filename1指定要移动的文件的位置和名称2.destination指定文件的新位置,目标可以由......
  • centOS6.5 无法使用yum源的问题 removing mirrorlist with no valid mirrors: /var/ca
     一次在临时服务器执行yum命令出现报错问题:removingmirrorlistwithnovalidmirrors:/var/cache/yum/x86_64/6/base/mirrorlist.txt ......1、修改fastestmirror.conf的配置参数sed-i"s|enabled=1|enabled=0|g"/etc/yum/pluginconf.d/fastestmirror.conf2、备份......
  • tar: Removing leading `/' from member names
    在执行压缩文件命令时,出现tar:Removingleading`/'frommembernames的问题,详情如下:dates=$(date-dyesterday+%F%m%d)tar-zcvf/root/backup/$dates.tar.gz/usr/bigdata/logs/$dates使用mantar命令查看,发现有一个-P选项,不从文件名中分离"/"。 ......
  • [AGC033C] Removing Coins题解
    思路可以看出,每次对一个点\(u\)操作一次,就相当于删除以\(u\)为根的所有叶节点。当然我们还是没有什么思路,我们可以想简单一点:在一条链上的情况。如果\(u\)是链的端点:以\(u\)为根节点的叶节点只有一个,所以链的长度减一。如果\(u\)不是链的端点:以\(u\)为根节点......
  • OGG报错 INS-85054 in oggca.sh createing a new Service Manager after removing a p
    这个报错主要是ogg的自启动和目录问题DeletethefollowingfilesattheOSlevel:Linux7/etc/systemd/system/OracleGoldenGate.service/etc/oggInst.locLinux6/etc/init.d/OracleGoldenGate/etc/rc.d/*OracleGoldenGate/etc/rc*.d/*OracleGoldenGate/etc/oggInst......
  • MPEG(Moving Picture Experts Group)协议发展史
    MPEG(MovingPictureExpertsGroup)是一个国际标准化组织,致力于制定数字多媒体编码标准。MPEG协议的发展史可以追溯到20世纪80年代初。以下是MPEG协议的主要发展历程:MPEG-1:发布时间:1993年MPEG-1是MPEG协议的第一个版本,主要用于压缩视频和音频。它最著名的应用之一是VideoCD(VCD),这是......