The Shortest Statement (Codeforces 1051F)
Tags: Others, shortest paths

You are given a weighed undirected connected graph, consisting of $$$n$$$ vertices and $$$m$$$ edges.You should answer $$$q$$$ queries, the $$$i$$$-th query is to find the shortest distance between vertices $$$u_i$$$ and $$$v_i$$$.

Input: The first line contains two integers $$$n$$$ and $$$m~(1 \le n, m \le 10^5, m - n \le 20)$$$ — the number of vertices and edges in the graph.Next $$$m$$$ lines contain the edges: the $$$i$$$-th edge is a triple of integers $$$v_i, u_i, d_i~(1 \le u_i, v_i \le n, 1 \le d_i \le 10^9, u_i \neq v_i)$$$. This triple means that there is an edge between vertices $$$u_i$$$ and $$$v_i$$$ of weight $$$d_i$$$. It is guaranteed that graph contains no self-loops and multiple edges.The next line contains a single integer $$$q~(1 \le q \le 10^5)$$$ — the number of queries.Each of the next $$$q$$$ lines contains two integers $$$u_i$$$ and $$$v_i~(1 \le u_i, v_i \le n)$$$ — descriptions of the queries.Pay attention to the restriction $$$m - n ~ \le ~ 20$$$.

Output: Print $$$q$$$ lines.The $$$i$$$-th line should contain the answer to the $$$i$$$-th query — the shortest distance between vertices $$$u_i$$$ and $$$v_i$$$.


Sample Inputs:
3 3
1 2 3
2 3 1
3 1 5
3
1 2
1 3
2 3

8 13
1 2 4
2 3 6
3 4 1
4 5 12
5 6 3
6 7 8
7 8 7
1 4 1
1 8 3
2 6 9
2 7 1
4 6 3
6 8 2
8
1 5
1 7
2 3
2 8
3 7
3 4
6 8
7 8

Sample Outputs:
3
4
1

7
5
6
7
7
1
2
7

Solution (Python):
from collections import deque
import heapq
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
        size[rs] += size[rt]
    else:
        root[rs] = rt
        size[rt] += size[rs]
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def get_size(s):
    return size[get_root(s)]

def bfs(s):
    q = deque()
    q.append(s)
    dist = [-1] * (n + 1)
    dist[s] = 0
    dist1 = [-1] * (n + 1)
    dist1[s] = 0
    parent = [-1] * (n + 1)
    while q:
        i = q.popleft()
        (di, di1) = (dist[i], dist1[i])
        for (j, d) in H[i]:
            if dist[j] == -1:
                dist[j] = di + d
                dist1[j] = di1 + 1
                q.append(j)
                parent[j] = i
    return (dist, dist1, parent)

def dijkstra(s):
    inf = pow(10, 14) + 1
    dist = [inf] * (n + 1)
    dist[s] = 0
    visit = [0] * (n + 1)
    p = []
    heapq.heappush(p, (dist[s], s))
    while p:
        (d, u) = heapq.heappop(p)
        if dist[u] < d:
            continue
        visit[u] = 1
        for (v, c) in G[u]:
            nd = dist[u] + c
            if not visit[v] and nd < dist[v]:
                dist[v] = nd
                heapq.heappush(p, (dist[v], v))
    return dist
(n, m) = map(int, input().split())
G = [[] for _ in range(n + 1)]
H = [[] for _ in range(n + 1)]
root = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]
size = [1 for _ in range(n + 1)]
s = set()
for _ in range(m):
    (u, v, d) = map(int, input().split())
    G[u].append((v, d))
    G[v].append((u, d))
    if not same(u, v):
        unite(u, v)
        H[u].append((v, d))
        H[v].append((u, d))
    else:
        s.add(u)
(dist, dist1, parent) = bfs(1)
dp0 = list(parent)
dp = [list(dp0)]
pow2 = [1]
for _ in range(18):
    pow2.append(2 * pow2[-1])
for _ in range(19):
    dp1 = [-1] * (n + 1)
    for i in range(1, n + 1):
        if dp0[i] == -1:
            continue
        dp1[i] = dp0[dp0[i]]
    dp.append(list(dp1))
    dp0 = list(dp1)
x = [dijkstra(i) for i in s]
q = int(input())
ans = []
for _ in range(q):
    (u, v) = map(int, input().split())
    (u0, v0) = (u, v)
    if dist1[u] > dist1[v]:
        (u, v) = (v, u)
    d = dist1[v] - dist1[u]
    for i in range(19):
        if d & pow2[i]:
            d ^= pow2[i]
            v = dp[i][v]
    if u ^ v:
        for i in range(18, -1, -1):
            if dist1[u] < pow2[i]:
                continue
            nu = dp[i][u]
            nv = dp[i][v]
            if nu ^ nv:
                (u, v) = (nu, nv)
    if u ^ v:
        v = parent[v]
    ans0 = dist[u0] + dist[v0] - 2 * dist[v]
    for x0 in x:
        ans0 = min(ans0, x0[u0] + x0[v0])
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]

class LowestCommonAncestor:
    """"""

    def __init__(self, G: '隣接リスト', root: '根', parents):
        from collections import deque
        self.n = len(G)
        self.tour = [0] * (2 * self.n - 1)
        self.depth_list = [0] * (2 * self.n - 1)
        self.id = [-1] * self.n
        self.dfs(G, root, parents)
        self._rmq_init(self.depth_list)

    def _rmq_init(self, arr):
        n = self.mod = len(arr)
        self.seg_len = 1 << (n - 1).bit_length()
        self.seg = [self.n * n] * (2 * self.seg_len)
        seg = self.seg
        for (i, e) in enumerate(arr):
            seg[self.seg_len + i] = n * e + i
        for i in range(self.seg_len - 1, 0, -1):
            seg[i] = min(seg[2 * i], seg[2 * i + 1])

    def _rmq_query(self, l, r):
        """"""
        l += self.seg_len
        r += self.seg_len
        res = self.n * self.mod
        seg = self.seg
        while l < r:
            if r & 1:
                r -= 1
                res = min(res, seg[r])
            if l & 1:
                res = min(res, seg[l])
                l += 1
            l >>= 1
            r >>= 1
        return res % self.mod

    def dfs(self, G, root, parents):
        """"""
        id = self.id
        tour = self.tour
        depth_list = self.depth_list
        v = root
        it = [0] * self.n
        visit_id = 0
        depth = 0
        while v != -1:
            if id[v] == -1:
                id[v] = visit_id
            tour[visit_id] = v
            depth_list[visit_id] = depth
            visit_id += 1
            g = G[v]
            if it[v] == len(g):
                v = parents[v]
                depth -= 1
                continue
            if g[it[v]] == parents[v]:
                it[v] += 1
                if it[v] == len(g):
                    v = parents[v]
                    depth -= 1
                    continue
                else:
                    child = g[it[v]]
                    it[v] += 1
                    v = child
                    depth += 1
            else:
                child = g[it[v]]
                it[v] += 1
                v = child
                depth += 1

    def lca(self, u: int, v: int) -> int:
        """"""
        (l, r) = (self.id[u], self.id[v])
        if r < l:
            (l, r) = (r, l)
        q = self._rmq_query(l, r + 1)
        return self.tour[q]

    def dist(self, u: int, v: int) -> int:
        """"""
        lca = self.lca(u, v)
        depth_u = self.depth_list[self.id[u]]
        depth_v = self.depth_list[self.id[v]]
        depth_lca = self.depth_list[self.id[lca]]
        return depth_u + depth_v - 2 * depth_lca
(n, m) = map(int, input().split())
edge = [[] for i in range(n)]
for _ in range(m):
    (x, y, z) = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append((y, z))
    edge[y].append((x, z))
depth = [0] * n
par = [-2] * n
par[0] = -1
todo = [(0, -1)]
tree = [[] for i in range(n)]
tree_edge = [[] for i in range(n)]
rem = set()
while todo:
    (v, p) = todo.pop()
    for (u, d) in edge[v]:
        if p == u:
            continue
        if par[u] != -2:
            rem.add((min(v, u), max(v, u), d))
        else:
            tree[u].append((v, d))
            tree[v].append((u, d))
            tree_edge[u].append(v)
            tree_edge[v].append(u)
            par[u] = v
            depth[u] = depth[v] + d
            todo.append((u, v))
rem = list(rem)
lca = LowestCommonAncestor(tree_edge, 0, par)

def query(x, y):
    z = lca.lca(x, y)
    return depth[x] + depth[y] - 2 * depth[z]
s = set()
for (x, y, z) in rem:
    s.add(x)
    s.add(y)
s = list(s)
id = [-1] * n
ns = len(s)
for i in range(ns):
    id[s[i]] = i
dist = [[10 ** 18] * ns for i in range(ns)]
for u in s:
    for v in s:
        idu = id[u]
        idv = id[v]
        dist[idu][idv] = query(u, v)
for (u, v, d) in rem:
    idu = id[u]
    idv = id[v]
    dist[idu][idv] = min(d, dist[idu][idv])
    dist[idv][idu] = min(d, dist[idv][idu])
for k in range(ns):
    for i in range(ns):
        for j in range(ns):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

def dfs(root):
    depth = [-1] * n
    depth[root] = 0
    todo = [root]
    while todo:
        v = todo.pop()
        for (to, d) in tree[v]:
            if depth[to] == -1:
                depth[to] = depth[v] + d
                todo.append(to)
    return depth
for k in range(ns):
    for i in range(ns):
        for j in range(ns):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
dist2 = []
for i in s:
    dist2.append(dfs(i))
ANS = []
q = int(input())
for _ in range(q):
    (u, v) = map(lambda x: int(x) - 1, input().split())
    ans = query(u, v)
    for i in range(ns):
        for j in range(ns):
            d = dist2[i][v] + dist[i][j] + dist2[j][u]
            ans = min(ans, d)
    ANS.append(ans)
print('\n'.join(map(str, ANS)))

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]

class LowestCommonAncestor:
    """"""

    def __init__(self, G: '隣接リスト', root: '根', parents):
        from collections import deque
        self.n = len(G)
        self.tour = [0] * (2 * self.n - 1)
        self.depth_list = [0] * (2 * self.n - 1)
        self.id = [-1] * self.n
        self.dfs(G, root, parents)
        self._rmq_init(self.depth_list)

    def _rmq_init(self, arr):
        n = self.mod = len(arr)
        self.seg_len = 1 << (n - 1).bit_length()
        self.seg = [self.n * n] * (2 * self.seg_len)
        seg = self.seg
        for (i, e) in enumerate(arr):
            seg[self.seg_len + i] = n * e + i
        for i in range(self.seg_len - 1, 0, -1):
            seg[i] = min(seg[2 * i], seg[2 * i + 1])

    def _rmq_query(self, l, r):
        """"""
        l += self.seg_len
        r += self.seg_len
        res = self.n * self.mod
        seg = self.seg
        while l < r:
            if r & 1:
                r -= 1
                res = min(res, seg[r])
            if l & 1:
                res = min(res, seg[l])
                l += 1
            l >>= 1
            r >>= 1
        return res % self.mod

    def dfs(self, G, root, parents):
        """"""
        id = self.id
        tour = self.tour
        depth_list = self.depth_list
        v = root
        it = [0] * self.n
        visit_id = 0
        depth = 0
        while v != -1:
            if id[v] == -1:
                id[v] = visit_id
            tour[visit_id] = v
            depth_list[visit_id] = depth
            visit_id += 1
            g = G[v]
            if it[v] == len(g):
                v = parents[v]
                depth -= 1
                continue
            if g[it[v]] == parents[v]:
                it[v] += 1
                if it[v] == len(g):
                    v = parents[v]
                    depth -= 1
                    continue
                else:
                    child = g[it[v]]
                    it[v] += 1
                    v = child
                    depth += 1
            else:
                child = g[it[v]]
                it[v] += 1
                v = child
                depth += 1

    def lca(self, u: int, v: int) -> int:
        """"""
        (l, r) = (self.id[u], self.id[v])
        if r < l:
            (l, r) = (r, l)
        q = self._rmq_query(l, r + 1)
        return self.tour[q]

    def dist(self, u: int, v: int) -> int:
        """"""
        lca = self.lca(u, v)
        depth_u = self.depth_list[self.id[u]]
        depth_v = self.depth_list[self.id[v]]
        depth_lca = self.depth_list[self.id[lca]]
        return depth_u + depth_v - 2 * depth_lca
(n, m) = map(int, input().split())
edge = [[] for i in range(n)]
for _ in range(m):
    (x, y, z) = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append((y, z))
    edge[y].append((x, z))
depth = [0] * n
par = [-2] * n
par[0] = -1
todo = [(0, -1)]
tree = [[] for i in range(n)]
tree_edge = [[] for i in range(n)]
rem = set()
while todo:
    (v, p) = todo.pop()
    for (u, d) in edge[v]:
        if p == u:
            continue
        if par[u] != -2:
            rem.add((min(v, u), max(v, u), d))
        else:
            tree[u].append((v, d))
            tree[v].append((u, d))
            tree_edge[u].append(v)
            tree_edge[v].append(u)
            par[u] = v
            depth[u] = depth[v] + d
            todo.append((u, v))
rem = list(rem)
lca = LowestCommonAncestor(tree_edge, 0, par)

def query(x, y):
    z = lca.lca(x, y)
    return depth[x] + depth[y] - 2 * depth[z]
s = set()
for (x, y, z) in rem:
    s.add(x)
    s.add(y)
s = list(s)
id = [-1] * n
ns = len(s)
for i in range(ns):
    id[s[i]] = i
dist = [[10 ** 18] * ns for i in range(ns)]
for u in s:
    for v in s:
        idu = id[u]
        idv = id[v]
        dist[idu][idv] = query(u, v)
for (u, v, d) in rem:
    idu = id[u]
    idv = id[v]
    dist[idu][idv] = min(d, dist[idu][idv])
    dist[idv][idu] = min(d, dist[idv][idu])
for k in range(ns):
    for i in range(ns):
        for j in range(ns):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

def dfs(root):
    depth = [-1] * n
    depth[root] = 0
    todo = [root]
    while todo:
        v = todo.pop()
        for (to, d) in tree[v]:
            if depth[to] == -1:
                depth[to] = depth[v] + d
                todo.append(to)
    return depth
for k in range(ns):
    for i in range(ns):
        for j in range(ns):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
dist2 = []
for i in s:
    dist2.append(dfs(i))
ANS = []
q = int(input())
for _ in range(q):
    (u, v) = map(lambda x: int(x) - 1, input().split())
    ans = query(u, v)
    for i in range(ns):
        for j in range(ns):
            d = dist2[i][v] + dist[i][j] + dist2[j][u]
            ans = min(ans, d)
    ANS.append(ans)
print('\n'.join(map(str, ANS)))