Graph Transpositions (Codeforces 1442C)
Tags: Greedy, shortest paths

You are given a directed graph of $$$n$$$ vertices and $$$m$$$ edges. Vertices are numbered from $$$1$$$ to $$$n$$$. There is a token in vertex $$$1$$$.The following actions are allowed:   Token movement. To move the token from vertex $$$u$$$ to vertex $$$v$$$ if there is an edge $$$u \to v$$$ in the graph. This action takes $$$1$$$ second.  Graph transposition. To transpose all the edges in the graph: replace each edge $$$u \to v$$$ by an edge $$$v \to u$$$. This action takes increasingly more time: $$$k$$$-th transposition takes $$$2^{k-1}$$$ seconds, i.e. the first transposition takes $$$1$$$ second, the second one takes $$$2$$$ seconds, the third one takes $$$4$$$ seconds, and so on. The goal is to move the token from vertex $$$1$$$ to vertex $$$n$$$ in the shortest possible time. Print this time modulo $$$998\,244\,353$$$.

Input: The first line of input contains two integers $$$n, m$$$ ($$$1 \le n, m \le 200\,000$$$).The next $$$m$$$ lines contain two integers each: $$$u, v$$$ ($$$1 \le u, v \le n; u \ne v$$$), which represent the edges of the graph. It is guaranteed that all ordered pairs $$$(u, v)$$$ are distinct.It is guaranteed that it is possible to move the token from vertex $$$1$$$ to vertex $$$n$$$ using the actions above.

Output: Print one integer: the minimum required time modulo $$$998\,244\,353$$$.

Note: The first example can be solved by transposing the graph and moving the token to vertex $$$4$$$, taking $$$2$$$ seconds.The best way to solve the second example is the following: transpose the graph, move the token to vertex $$$2$$$, transpose the graph again, move the token to vertex $$$3$$$, transpose the graph once more and move the token to vertex $$$4$$$.

Sample Inputs:
4 4
1 2
2 3
3 4
4 1

4 3
2 1
2 3
4 3

Sample Outputs:
2

10

Solution (Python):
from heapq import heappush, heappop
mod = 998244353
(N, M) = map(int, input().split())
E1 = [[] for _ in range(N)]
E2 = [[] for _ in range(N)]
for _ in range(M):
    (u, v) = map(int, input().split())
    u -= 1
    v -= 1
    E1[u].append(v)
    E2[v].append(u)
mask1 = (1 << 23) - 1
mask2 = (1 << 18) - 1
inf = 1 << 62
dist = [inf] * (1 << 23)
start = 0
dist[start] = 0
q = [start]
while q:
    v = heappop(q)
    dist_v = v >> 23
    v &= mask1
    n_trans = v >> 18
    v_node = v & mask2
    if v_node == N - 1:
        print(dist_v % mod)
        exit()
    if n_trans > 20:
        break
    if dist[v] != dist_v:
        continue
    for u_node in E1[v_node] if n_trans & 1 == 0 else E2[v_node]:
        u = n_trans << 18 | u_node
        dist_u = dist_v + 1
        if dist_u < dist[u]:
            dist[u] = dist_u
            heappush(q, dist_u << 23 | u)
    u = n_trans + 1 << 18 | v_node
    dist_u = dist_v + (1 << n_trans)
    if dist_u < dist[u]:
        dist[u] = dist_u
        heappush(q, dist_u << 23 | u)
mask1 = (1 << 37) - 1
mask2 = (1 << 19) - 1
mask3 = (1 << 18) - 1
REV = 1 << 18
dist = [inf] * (1 << 19)
start = 0
dist[start] = 0
q = [start]
while q:
    v = heappop(q)
    dist_v = v >> 19
    n_trans = dist_v >> 18
    v &= mask2
    v_node = v & mask3
    if v_node == N - 1:
        ans = pow(2, n_trans, mod) - 1 + (dist_v & mask3)
        print(ans)
        exit()
    rev = v & REV
    if dist[v] != dist_v:
        continue
    for u_node in E1[v_node] if n_trans & 1 == 0 else E2[v_node]:
        u = rev | u_node
        dist_u = dist_v + 1
        if dist_u < dist[u]:
            dist[u] = dist_u
            heappush(q, dist_u << 19 | u)
    u = v ^ REV
    dist_u = dist_v + (1 << 18)
    if dist_u < dist[u]:
        dist[u] = dist_u
        heappush(q, dist_u << 19 | u)
assert False

Solution (Python):
import math
import sys
import copy
import io
import os
from collections import deque, defaultdict
from queue import PriorityQueue
from heapq import heappop, heappush
input = sys.stdin.buffer.readline
sys.setrecursionlimit(int(300000.0))

class AC(object):

    def __init__(self):
        self.max_value = int(200000.0)
        self.mod = 998244353
        (self.n, self.m) = list(map(int, input().split()))
        self.edge_list = []
        for _ in range(self.m):
            (x, y) = list(map(int, input().split()))
            self.edge_list.append((x, y))
        ans = self.find(fn=lambda x: self.max_value)
        cnt = int(ans / self.max_value)
        if cnt >= 20:
            print((ans % self.max_value + pow(2, cnt, self.mod) - 1) % self.mod)
        else:
            print(self.find2())

    def find(self, fn):
        v = [[] for _ in range(self.n + 1)]
        rv = [[] for _ in range(self.n + 1)]
        for (x, y) in self.edge_list:
            v[x].append(y)
            rv[y].append(x)
        dis = [-1 for _ in range(self.n + 1)]
        rdis = [-1 for _ in range(self.n + 1)]
        inq = [False for _ in range(self.n + 1)]
        rinq = [False for _ in range(self.n + 1)]
        q = deque([1])
        rq = deque([])
        dis[1] = 0
        inq[1] = True
        tick = 0
        while q or rq:
            if tick % 2 == 0:
                self.cal_dis(v, dis, rdis, q, rq, inq, rinq, fn(tick))
            else:
                self.cal_dis(rv, rdis, dis, rq, q, rinq, inq, fn(tick))
            tick += 1
        return min(dis[self.n], rdis[self.n])

    def cal_dis(self, g, dis, rdis, q, rq, inq, rinq, ex):
        while q:
            x = q.popleft()
            inq[x] = False
            if dis[x] + ex < rdis[x] or rdis[x] == -1:
                rdis[x] = dis[x] + ex
                if not rinq[x]:
                    rinq[x] = True
                    rq.append(x)
            for y in g[x]:
                if dis[x] + 1 < dis[y] or dis[y] == -1:
                    dis[y] = dis[x] + 1
                    if not inq[y]:
                        inq[y] = True
                        q.append(y)

    def find2(self):
        self.inf = int(2000000000.0)
        v = [[] for _ in range(self.n + 1)]
        rv = [[] for _ in range(self.n + 1)]
        for (x, y) in self.edge_list:
            v[x].append(y)
            rv[y].append(x)
        dis = [self.inf for _ in range(self.n + 1)]
        rdis = [self.inf for _ in range(self.n + 1)]
        q = []
        rq = []
        heappush(q, (0, 1))
        dis[1] = 0
        tick = 0
        ans = self.inf
        while ans > 1 << tick:
            if tick % 2 == 0:
                self.dij(v, dis, rdis, q, rq, 1 << tick)
                ans = min(ans, dis[self.n])
            else:
                self.dij(rv, rdis, dis, rq, q, 1 << tick)
                ans = min(ans, rdis[self.n])
            tick += 1
        return ans

    def dij(self, g, dis, rdis, q, rq, ex):
        while q:
            (d, x) = heappop(q)
            if d == dis[x]:
                if d + ex < rdis[x]:
                    rdis[x] = d + ex
                    heappush(rq, (rdis[x], x))
                for y in g[x]:
                    if dis[x] + 1 < dis[y]:
                        dis[y] = dis[x] + 1
                        heappush(q, (dis[y], y))
if __name__ == '__main__':
    ac = AC()

Solution (Python):
import math
import sys
import copy
from collections import deque, defaultdict
from queue import PriorityQueue
from heapq import heappop, heappush
input = sys.stdin.buffer.readline
sys.setrecursionlimit(int(300000.0))

class AC(object):

    def __init__(self):
        self.max_value = int(200000.0)
        self.mod = 998244353
        (self.n, self.m) = list(map(int, input().split()))
        self.edge_list = []
        for _ in range(self.m):
            (x, y) = list(map(int, input().split()))
            self.edge_list.append((x, y))
        ans = self.find(fn=lambda x: self.max_value)
        cnt = int(ans / self.max_value)
        if cnt >= 20:
            print((ans % self.max_value + pow(2, cnt, self.mod) - 1) % self.mod)
        else:
            print(self.find2())

    def find(self, fn):
        v = [[] for _ in range(self.n + 1)]
        rv = [[] for _ in range(self.n + 1)]
        for (x, y) in self.edge_list:
            v[x].append(y)
            rv[y].append(x)
        dis = [-1 for _ in range(self.n + 1)]
        rdis = [-1 for _ in range(self.n + 1)]
        inq = [False for _ in range(self.n + 1)]
        rinq = [False for _ in range(self.n + 1)]
        q = deque([1])
        rq = deque([])
        dis[1] = 0
        inq[1] = True
        tick = 0
        while q or rq:
            if tick % 2 == 0:
                self.cal_dis(v, dis, rdis, q, rq, inq, rinq, fn(tick))
            else:
                self.cal_dis(rv, rdis, dis, rq, q, rinq, inq, fn(tick))
            tick += 1
        return min(dis[self.n], rdis[self.n])

    def cal_dis(self, g, dis, rdis, q, rq, inq, rinq, ex):
        while q:
            x = q.popleft()
            inq[x] = False
            if dis[x] + ex < rdis[x] or rdis[x] == -1:
                rdis[x] = dis[x] + ex
                if not rinq[x]:
                    rinq[x] = True
                    rq.append(x)
            for y in g[x]:
                if dis[x] + 1 < dis[y] or dis[y] == -1:
                    dis[y] = dis[x] + 1
                    if not inq[y]:
                        inq[y] = True
                        q.append(y)

    def find2(self):
        self.inf = int(2000000000.0)
        v = [[] for _ in range(self.n + 1)]
        rv = [[] for _ in range(self.n + 1)]
        for (x, y) in self.edge_list:
            v[x].append(y)
            rv[y].append(x)
        dis = [self.inf for _ in range(self.n + 1)]
        rdis = [self.inf for _ in range(self.n + 1)]
        q = []
        rq = []
        heappush(q, (0, 1))
        dis[1] = 0
        tick = 0
        ans = self.inf
        while ans > 1 << tick:
            if tick % 2 == 0:
                self.dij(v, dis, rdis, q, rq, 1 << tick)
                ans = min(ans, dis[self.n])
            else:
                self.dij(rv, rdis, dis, rq, q, 1 << tick)
                ans = min(ans, rdis[self.n])
            tick += 1
        return ans

    def dij(self, g, dis, rdis, q, rq, ex):
        while q:
            (d, x) = heappop(q)
            if d == dis[x]:
                if d + ex < rdis[x]:
                    rdis[x] = d + ex
                    heappush(rq, (rdis[x], x))
                for y in g[x]:
                    if dis[x] + 1 < dis[y]:
                        dis[y] = dis[x] + 1
                        heappush(q, (dis[y], y))
if __name__ == '__main__':
    ac = AC()