Time Travel (Codeforces 1888E)
Tags: Implement, shortest paths

Berland is a country with ancient history, where roads were built and destroyed for centuries. It is known that there always were $$$n$$$ cities in Berland. You also have records of $$$t$$$ key moments in the history of the country, numbered from $$$1$$$ to $$$t$$$. Each record contains a list of bidirectional roads between some pairs of cities, which could be used for travel in Berland at a specific moment in time.You have discovered a time machine that transports you between key moments. Unfortunately, you cannot choose what point in time to end up at, but you know the order consisting of $$$k$$$ moments in time $$$a_{i}$$$, in which the machine will transport you. Since there is little time between the travels, when you find yourself in the next key moment in time (including after the last time travel), you can travel on at most one existing road at that moment, coming out from the city you were in before time travel.Currently, you are in city $$$1$$$, and the time machine has already transported you to moment $$$a_{1}$$$. You want to reach city $$$n$$$ as quickly as possible. Determine the minimum number of time travels, including the first one, that you need to make in order to reach city $$$n$$$.

Input: The first line contains two integers $$$n$$$ and $$$t$$$ ($$$2 \le n \le 2 \cdot 10^5, 1 \le t \le 2 \cdot 10^5$$$) — the number of cities in Berland and the number of records about key moments in history. Then follows the description of each of the $$$t$$$ records.The first line of each record description contains a single integer $$$m_{i}$$$ ($$$0 \le m_{i} \le \min \left(\frac{n(n-1)}{2}, 2 \cdot 10^5\right)$$$) — the number of roads in the $$$i$$$-th record.Each of the next $$$m_i$$$ lines contains two integers $$$v_{j}$$$ and $$$u_{j}$$$ ($$$1 \le v_{j}, u_{j} \le n$$$, $$$v_{j} \neq u_{j}$$$) — the numbers of cities connected by the $$$j$$$-th road in the $$$i$$$-th key moment in history.The next line contains a single integer $$$k$$$ ($$$1 \le k \le 2 \cdot 10^5$$$) — the number of time moments between which movements will occur.The next line contains $$$k$$$ integers $$$a_1, a_2, \ldots, a_k$$$ ($$$1 \le a_{i} \le t$$$) — the time moments at which you will be after each movement.It is guaranteed that the sum of $$$m_{i}$$$ does not exceed $$$2 \cdot 10^5$$$. It is guaranteed that each unordered pair $$$(u, v)$$$ occurs in the road description for one record no more than once.

Output: Output a single integer — the minimum number of time travels required to reach city $$$n$$$ from city $$$1$$$, or $$$-1$$$ if it is impossible.Note that movement to time moment $$$a_{1}$$$ is also considered a movement.

Note: In the first example, you are in city $$$1$$$ and move to moment $$$a_{1} = 2$$$. Since there are no suitable roads to pass, you do nothing and move to moment $$$a_{2} = 1$$$, after which you travel along the road $$$(1, 2)$$$. Moving to moment $$$a_{3} = 2$$$, you travel along the road $$$(2, 3)$$$. Moving to moment $$$a_{4} = 1$$$, you stay in city $$$3$$$ and make the next time travel. At time moment $$$a_{5} = 2$$$, you travel along the road $$$(3, 5)$$$ and end up in the final city after $$$5$$$ time travels.In the second example, it can be shown that it is impossible to reach city $$$5$$$ with the given time travels.

Sample Inputs:
5 2
4
1 2
2 3
3 4
4 5
2
2 3
3 5
6
2 1 2 1 2 1

5 2
3
1 2
3 1
4 3
2
2 1
4 5
5
1 2 1 1 1

Sample Outputs:
5

-1

Solution (Python):
import bisect
from heapq import heappop, heappush
from sys import stdin
(n, t) = map(int, input().split())
roads = []
vis = [False] * n
g = [[] for _ in range(n)]
for x in range(t):
    m = int(input())
    for _ in range(m):
        (u, v) = map(int, stdin.readline()[:-1].split())
        u -= 1
        v -= 1
        g[u].append((x, v))
        g[v].append((x, u))
k = int(input())
a = list(map(int, stdin.readline()[:-1].split()))
q = [(0, 0)]
queues = [[] for _ in range(t)]
for i in range(k):
    queues[a[i] - 1].append(i)
while q:
    (dis, u) = heappop(q)
    if vis[u]:
        continue
    if u == n - 1:
        print(dis)
        exit()
    vis[u] = True
    for (c, v) in g[u]:
        if not queues[c] or dis > queues[c][-1]:
            continue
        ind = bisect.bisect_left(queues[c], dis)
        heappush(q, (queues[c][ind] + 1, v))
print(-1)

Solution (Python):
import decimal
import gc
import heapq
import math
import operator
import os
import random
import sys
from collections import Counter, deque, defaultdict, OrderedDict
from copy import copy
from fractions import Fraction
from io import BytesIO, IOBase
import bisect
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def bucketsort(order, seq):
    buckets = [0] * (max(seq) + 1)
    for x in seq:
        buckets[x] += 1
    for i in range(len(buckets) - 1):
        buckets[i + 1] += buckets[i]
    new_order = [-1] * len(seq)
    for i in reversed(order):
        x = seq[i]
        idx = buckets[x] = buckets[x] - 1
        new_order[idx] = i
    return new_order

def ordersort(order, seq, reverse=False):
    bit = max(seq).bit_length() >> 1
    mask = (1 << bit) - 1
    order = bucketsort(order, [x & mask for x in seq])
    order = bucketsort(order, [x >> bit for x in seq])
    if reverse:
        order.reverse()
    return order

def isPrime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i = i + 6
    return True

def lcm(a, b):
    return a * b // math.gcd(a, b)

def ciel(a, b):
    x = a // b
    if a % b == 0:
        return x
    return x + 1

def ints_get():
    return map(int, input().strip().split())

def list_get():
    return list(map(int, sys.stdin.readline().strip().split()))

def chars_get():
    return list(map(str, sys.stdin.readline().strip().split()))

def ipn():
    return int(input())

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def main():
    (n, t) = ints_get()
    d = defaultdict(list)
    for i in range(t):
        for _ in range(ipn()):
            (a, b) = ints_get()
            d[a].append([b, i + 1])
            d[b].append([a, i + 1])
    k = ipn()
    a = list_get()
    vis = [10 ** 9] * (n + 1)
    vis[1] = 0
    v = [[] for _ in range(t + 1)]
    for (i, j) in d[1]:
        v[j].append(i)
    d[1].clear()
    for i in range(k):
        p = v[a[i]].copy()
        v[a[i]].clear()
        for j in p:
            if vis[j] == 10 ** 9:
                vis[j] = i + 1
                for (x, y) in d[j]:
                    v[y].append(x)
                d[j].clear()
    if vis[-1] == 10 ** 9:
        print(-1)
    else:
        print(vis[-1])
    return
if __name__ == '__main__':
    main()

Solution (Python):
import sys
ipt = sys.stdin.readline
from collections import defaultdict

def iin():
    return int(ipt())

def lmin():
    return list(map(int, ipt().split()))
(N, T) = lmin()
era = [[] for _ in range(T)]
place = [[] for _ in range(N)]
for i in range(T):
    M = iin()
    for _ in range(M):
        (u, v) = lmin()
        (u, v) = (u - 1, v - 1)
        place[u].append((i, v))
        place[v].append((i, u))
for (e, nxt) in place[0]:
    era[e].append((0, nxt))
input()
A = lmin()
visited = [0] * N
visited[0] = 1
for (i, E) in enumerate(A):
    E -= 1
    t_era = era[E][:]
    era[E] = []
    while t_era:
        (cur, nxt) = t_era.pop()
        if visited[nxt]:
            continue
        visited[nxt] = 1
        for (e, nxt2) in place[nxt]:
            era[e].append((nxt, nxt2))
    if visited[N - 1]:
        print(i + 1)
        exit()
print(-1)