Moving Platforms (Codeforces 1932G)
Tags: Math, shortest paths

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$$$.

Note: This is how levels of the platforms change, and what actions we need to perform in the first example.Platform 1Platform 2Platform 3ActionStep 1194Stay on the platform 1Step 2324Stay on the platform 1Step 3554Move to the platform 2Step 4784Stay on the platform 2Step 5914Stay on the platform 2Step 6144Move to the platform 3

Sample Inputs:
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

Sample Outputs:
6
-1
52

Solution (Python):
import sys
import heapq
inf = 10 ** 18

def gcd(a, b):
    while b:
        (a, b) = (b, a % b)
    return a
for _ in range(int(input())):
    (n, m, H) = map(int, sys.stdin.readline().split())
    L = list(map(int, sys.stdin.readline().split()))
    S = list(map(int, sys.stdin.readline().split()))
    neighbor = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = map(int, sys.stdin.readline().split())
        u -= 1
        v -= 1
        G = gcd(S[u] - S[v], H)
        if (L[v] - L[u]) % G == 0:
            A = (S[u] - S[v]) // G
            B = (L[v] - L[u]) // G
            C = H // G
            neighbor[u].append([v, B * pow(A, -1, C) % C, C])
            neighbor[v].append([u, B * pow(A, -1, C) % C, C])
    dist = [inf] * n
    dist[0] = -1
    visited = [0] * n
    pq = [(dist[0], 0)]
    while pq:
        (d, u) = heapq.heappop(pq)
        if visited[u]:
            continue
        visited[u] = 1
        for (v, w, mod) in neighbor[u]:
            if not visited[v]:
                new_dist = w + mod * ((d - w) // mod + 1)
                if new_dist < dist[v]:
                    dist[v] = new_dist
                    heapq.heappush(pq, (new_dist, v))
    if dist[n - 1] == inf:
        print(-1)
    else:
        print(dist[n - 1] + 1)

Solution (Python):
def extended_gcd(a, b):
    """"""
    (s, old_s) = (0, 1)
    (r, old_r) = (b, a)
    while r:
        q = old_r // r
        (old_r, r) = (r, old_r - q * r)
        (old_s, s) = (s, old_s - q * s)
    return (old_r, old_s, (old_r - old_s * a) // b if b else 0)

def modinv(a, m):
    """"""
    (g, x, _) = extended_gcd(a % m, m)
    return x % m if g == 1 else None

def f(initial_diff, diff_change, mod):
    """"""
    g = gcd(diff_change, mod)
    if initial_diff % g != 0:
        return (-1, -1)
    initial_diff //= g
    diff_change //= g
    mod //= g
    base = -initial_diff % mod * modinv(diff_change, mod)
    base %= mod
    mul = mod
    return (base, mul)

def bruteforce_generate(initial_diff, diff_change, mod):
    """"""
    arr = []
    diff = initial_diff % mod
    for i in range(200):
        if diff == 0:
            arr.append(i)
        diff = (diff + diff_change) % mod
    return arr[:5]

def test():
    n = 10
    for initial_diff in range(n):
        for diff_change in range(1, n):
            for mod in range(1, n):
                (base, mul) = f(initial_diff, diff_change, mod)
                arr = bruteforce_generate(initial_diff, diff_change, mod)
                if base == -1:
                    assert len(arr) == 0
                else:
                    arr2 = []
                    x = base
                    for __ in range(5):
                        arr2.append(x)
                        x += mul
                    assert arr2 == arr, f'initial_diff={initial_diff} diff_change={diff_change} mod={mod} arr2={arr2} arr={arr} base={base} mod={mod}'
                print('ok')
    return
import heapq

def main():
    t = int(input())
    allans = []
    for ____ in range(t):
        (n, m, mod) = readIntArr()
        initial_level = readIntArr()
        change_level = readIntArr()
        adj = [[] for _ in range(n)]
        for _ in range(m):
            (u, v) = readIntArr()
            u -= 1
            v -= 1
            adj[u].append(v)
            adj[v].append(u)
        min_steps = [-1] * n
        min_steps[0] = 0
        h = [(0, 0)]
        while h:
            (steps, u) = heapq.heappop(h)
            if steps == min_steps[u]:
                for v in adj[u]:
                    initial_diff = initial_level[v] - initial_level[u]
                    initial_diff %= mod
                    diff_change = change_level[v] - change_level[u]
                    diff_change %= mod
                    (base, mul) = f(initial_diff, diff_change, mod)
                    if base != -1:
                        k = ceil((steps - base) / mul)
                        new_steps = base + k * mul + 1
                        if min_steps[v] == -1 or new_steps < min_steps[v]:
                            min_steps[v] = new_steps
                            heapq.heappush(h, (new_steps, v))
        ans = min_steps[n - 1]
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())

def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
from sys import stdin
from heapq import heappop, heappush
from math import gcd

def gcd_coef(a, b, c):
    assert a < b
    d = gcd(a, b)
    if c % d != 0:
        return None
    (init_a, init_b) = (a, b)
    (a_a, a_b) = (1, 0)
    (b_a, b_b) = (0, 1)
    while a > 0:
        (div, mod) = divmod(b, a)
        (a_a, a_b, b_a, b_b) = (b_a - div * a_a, b_b - div * a_b, a_a, a_b)
        (a, b) = (mod, a)
    assert d == b
    assert init_a * b_a + init_b * b_b == b
    return b_a * (c // d) % (init_b // d)

def solve():
    (n, m, H) = map(int, stdin.readline().split())
    levels = list(map(int, stdin.readline().split()))
    speeds = list(map(int, stdin.readline().split()))
    graph = [[] for i in range(n)]
    for i in range(m):
        (a, b) = [int(w) - 1 for w in stdin.readline().split()]
        graph[a].append(b)
        graph[b].append(a)
    inf = n * H
    heap = [(0, 0)]
    reach_time = [inf] * n
    while heap:
        (t, v) = heappop(heap)
        if t >= reach_time[v]:
            continue
        if v == n - 1:
            return t
        reach_time[v] = t
        for u in graph[v]:
            rel_speed = (speeds[u] - speeds[v]) % H
            diff = -(levels[u] - levels[v] + t * rel_speed) % H
            dt = gcd_coef(rel_speed, H, diff)
            if dt is not None and t + dt + 1 < reach_time[u]:
                heappush(heap, (t + dt + 1, u))
    return -1
n_tests = int(stdin.readline())
for test_id in range(n_tests):
    print(solve())