Cheap Robot (Codeforces 1253F)
Tags: Others, shortest paths

You're given a simple, undirected, connected, weighted graph with $$$n$$$ nodes and $$$m$$$ edges.Nodes are numbered from $$$1$$$ to $$$n$$$. There are exactly $$$k$$$ centrals (recharge points), which are nodes $$$1, 2, \ldots, k$$$.We consider a robot moving into this graph, with a battery of capacity $$$c$$$, not fixed by the constructor yet. At any time, the battery contains an integer amount $$$x$$$ of energy between $$$0$$$ and $$$c$$$ inclusive.Traversing an edge of weight $$$w_i$$$ is possible only if $$$x \ge w_i$$$, and costs $$$w_i$$$ energy points ($$$x := x - w_i$$$).Moreover, when the robot reaches a central, its battery is entirely recharged ($$$x := c$$$).You're given $$$q$$$ independent missions, the $$$i$$$-th mission requires to move the robot from central $$$a_i$$$ to central $$$b_i$$$.For each mission, you should tell the minimum capacity required to acheive it.

Input: The first line contains four integers $$$n$$$, $$$m$$$, $$$k$$$ and $$$q$$$ ($$$2 \le k \le n \le 10^5$$$ and $$$1 \le m, q \le 3 \cdot 10^5$$$).The $$$i$$$-th of the next $$$m$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$ and $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$, $$$1 \le w_i \le 10^9$$$), that mean that there's an edge between nodes $$$u$$$ and $$$v$$$, with a weight $$$w_i$$$.It is guaranteed that the given graph is simple (there is no self-loop, and there is at most one edge between every pair of nodes) and connected.The $$$i$$$-th of the next $$$q$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le k$$$, $$$a_i \neq b_i$$$).

Output: You have to output $$$q$$$ lines, where the $$$i$$$-th line contains a single integer : the minimum capacity required to acheive the $$$i$$$-th mission.

Note: In the first example, the graph is the chain $$$10 - 9 - 2^C - 4 - 1^C - 5 - 7 - 3^C - 8 - 6$$$, where centrals are nodes $$$1$$$, $$$2$$$ and $$$3$$$.For the mission $$$(2, 3)$$$, there is only one simple path possible. Here is a simulation of this mission when the capacity is $$$12$$$.  The robot begins on the node $$$2$$$, with $$$c = 12$$$ energy points.  The robot uses an edge of weight $$$4$$$. The robot reaches the node $$$4$$$, with $$$12 - 4 = 8$$$ energy points.  The robot uses an edge of weight $$$8$$$. The robot reaches the node $$$1$$$ with $$$8 - 8 = 0$$$ energy points.  The robot is on a central, so its battery is recharged. He has now $$$c = 12$$$ energy points.  The robot uses an edge of weight $$$2$$$. The robot is on the node $$$5$$$, with $$$12 - 2 = 10$$$ energy points.  The robot uses an edge of weight $$$3$$$. The robot is on the node $$$7$$$, with $$$10 - 3 = 7$$$ energy points.  The robot uses an edge of weight $$$2$$$. The robot is on the node $$$3$$$, with $$$7 - 2 = 5$$$ energy points.  The robot is on a central, so its battery is recharged. He has now $$$c = 12$$$ energy points.  End of the simulation. Note that if value of $$$c$$$ was lower than $$$12$$$, we would have less than $$$8$$$ energy points on node $$$4$$$, and we would be unable to use the edge $$$4 \leftrightarrow 1$$$ of weight $$$8$$$. Hence $$$12$$$ is the minimum capacity required to acheive the mission.—The graph of the second example is described here (centrals are red nodes):  The robot can acheive the mission $$$(3, 1)$$$ with a battery of capacity $$$c = 38$$$, using the path $$$3 \rightarrow 9 \rightarrow 8 \rightarrow 7 \rightarrow 2 \rightarrow 7 \rightarrow 6 \rightarrow 5 \rightarrow 4 \rightarrow 1$$$The robot can acheive the mission $$$(2, 3)$$$ with a battery of capacity $$$c = 15$$$, using the path $$$2 \rightarrow 7 \rightarrow 8 \rightarrow 9 \rightarrow 3$$$

Sample Inputs:
10 9 3 1
10 9 11
9 2 37
2 4 4
4 1 8
1 5 2
5 7 3
7 3 2
3 8 4
8 6 13
2 3

9 11 3 2
1 3 99
1 4 5
4 5 3
5 6 3
6 4 11
6 7 21
7 2 6
7 8 4
8 9 3
9 2 57
9 3 2
3 1
2 3

Sample Outputs:
12

38
15

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

def make_graph(n, m):
    (x, y, s) = ([0] * (2 * m), [0] * (2 * m), [0] * (n + 3))
    for i in range(0, 2 * m, 2):
        (u, v, w) = map(int, input().split())
        s[u + 2] += 1
        s[v + 2] += 1
        (x[i], x[i + 1]) = (u, v)
        (y[i], y[i + 1]) = (w, w)
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    (G, W) = ([0] * (2 * m), [0] * (2 * m))
    for i in range(2 * m):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        W[s[j]] = y[i ^ 1]
        s[j] += 1
    return (G, W, s, x, y)

def f(u, v):
    return u * l + v

def dijkstra():
    dist = [inf] * (n + 1)
    color = [0] * (n + 1)
    visit = [0] * (n + 1)
    p = []
    for i in range(1, k + 1):
        dist[i] = 0
        color[i] = i
        heapq.heappush(p, f(dist[i], i))
    while p:
        (d, u) = divmod(heapq.heappop(p), l)
        if visit[u]:
            continue
        visit[u] = 1
        for i in range(s0[u], s0[u + 1]):
            (v, c) = (G[i], W[i])
            nd = d + c
            if not visit[v] and nd < dist[v]:
                dist[v] = nd
                color[v] = color[u]
                heapq.heappush(p, f(dist[v], v))
    return (dist, color)

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):
    (s, t) = (get_root(s), get_root(t))
    if s == t:
        return
    if rank[s] < rank[t]:
        (s, t) = (t, s)
    if rank[s] == rank[t]:
        rank[s] += 1
    root[t] = s
    size[s] += size[t]
    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)]
(n, m, k, q) = map(int, input().split())
l = max(n, m) + 1
(G, W, s0, x, y) = make_graph(n, m)
inf = pow(10, 15) + 1
(dist, color) = dijkstra()
z = []
for i in range(m):
    (u, v) = (x[2 * i], x[2 * i + 1])
    if color[u] ^ color[v]:
        z.append(f(dist[u] + dist[v] + y[2 * i], i))
e = [set() for _ in range(k + 1)]
for i in range(q):
    (a, b) = map(int, input().split())
    e[a].add(i)
    e[b].add(i)
root = [i for i in range(k + 1)]
rank = [1 for _ in range(k + 1)]
size = [1 for _ in range(k + 1)]
ans = [0] * q
for z0 in sorted(z):
    (c, i) = divmod(z0, l)
    (u, v) = (color[x[2 * i]], color[x[2 * i + 1]])
    (u, v) = (get_root(u), get_root(v))
    if same(u, v):
        continue
    unite(u, v)
    if u ^ get_root(u):
        (u, v) = (v, u)
    if len(e[u]) < len(e[v]):
        (e[u], e[v]) = (e[v], e[u])
    eu = e[u]
    for i in e[v]:
        if i in eu:
            ans[i] = c
            eu.remove(i)
        else:
            eu.add(i)
    e[v].clear()
sys.stdout.write('\n'.join(map(str, ans)))

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

def make_graph(n, m):
    (x, y, s) = ([0] * (2 * m), [0] * (2 * m), [0] * (n + 3))
    for i in range(0, 2 * m, 2):
        (u, v, w) = map(int, input().split())
        s[u + 2] += 1
        s[v + 2] += 1
        (x[i], x[i + 1]) = (u, v)
        (y[i], y[i + 1]) = (w, w)
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    (G, W) = ([0] * (2 * m), [0] * (2 * m))
    for i in range(2 * m):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        W[s[j]] = y[i ^ 1]
        s[j] += 1
    return (G, W, s, x, y)

def f(u, v):
    return u * l + v

def dijkstra():
    dist = [inf] * (n + 1)
    color = [0] * (n + 1)
    visit = [0] * (n + 1)
    p = []
    for i in range(1, k + 1):
        dist[i] = 0
        color[i] = i
        heapq.heappush(p, f(dist[i], i))
    while p:
        (d, u) = divmod(heapq.heappop(p), l)
        if visit[u]:
            continue
        visit[u] = 1
        for i in range(s0[u], s0[u + 1]):
            (v, c) = (G[i], W[i])
            nd = d + c
            if not visit[v] and nd < dist[v]:
                dist[v] = nd
                color[v] = color[u]
                heapq.heappush(p, f(dist[v], v))
    return (dist, color)

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):
    (s, t) = (get_root(s), get_root(t))
    if s == t:
        return
    if rank[s] < rank[t]:
        (s, t) = (t, s)
    if rank[s] == rank[t]:
        rank[s] += 1
    root[t] = s
    size[s] += size[t]
    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)]
(n, m, k, q) = map(int, input().split())
l = max(n, m) + 1
(G, W, s0, x, y) = make_graph(n, m)
inf = pow(10, 15) + 1
(dist, color) = dijkstra()
z = []
for i in range(m):
    (u, v) = (x[2 * i], x[2 * i + 1])
    if color[u] ^ color[v]:
        z.append(f(dist[u] + dist[v] + y[2 * i], i))
e = [set() for _ in range(k + 1)]
for i in range(q):
    (a, b) = map(int, input().split())
    e[a].add(i)
    e[b].add(i)
root = [i for i in range(k + 1)]
rank = [1 for _ in range(k + 1)]
size = [1 for _ in range(k + 1)]
ans = [0] * q
for z0 in sorted(z):
    (c, i) = divmod(z0, l)
    (u, v) = (color[x[2 * i]], color[x[2 * i + 1]])
    (u, v) = (get_root(u), get_root(v))
    if same(u, v):
        continue
    unite(u, v)
    if u ^ get_root(u):
        (u, v) = (v, u)
    if len(e[u]) < len(e[v]):
        (e[u], e[v]) = (e[v], e[u])
    eu = e[u]
    for i in e[v]:
        if i in eu:
            ans[i] = c
            eu.remove(i)
        else:
            eu.add(i)
    e[v].clear()
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
(standard_input, packages, output_together) = (1, 1, 1)
(dfs, hashing, read_from_file) = (0, 0, 0)
de = 1
if 1:
    if standard_input:
        import io, os, sys
        input = lambda : sys.stdin.readline().strip()
        inf = float('inf')

        def I():
            return input()

        def II():
            return int(input())

        def MII():
            return map(int, input().split())

        def LI():
            return list(input().split())

        def LII():
            return list(map(int, input().split()))

        def LFI():
            return list(map(float, input().split()))

        def GMI():
            return map(lambda x: int(x) - 1, input().split())

        def LGMI():
            return list(map(lambda x: int(x) - 1, input().split()))
    if packages:
        from io import BytesIO, IOBase
        import math
        import random
        import os
        import bisect
        import typing
        from collections import Counter, defaultdict, deque
        from copy import deepcopy
        from functools import cmp_to_key, lru_cache, reduce
        from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
        from itertools import accumulate, combinations, permutations, count, product
        from operator import add, iand, ior, itemgetter, mul, xor
        from string import ascii_lowercase, ascii_uppercase, ascii_letters
        from typing import *
        BUFSIZE = 4096
    if output_together:

        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.stdout = IOWrapper(sys.stdout)
    if dfs:
        from types import GeneratorType

        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
    if hashing:
        RANDOM = random.getrandbits(20)

        class Wrapper(int):

            def __init__(self, x):
                int.__init__(x)

            def __hash__(self):
                return super(Wrapper, self).__hash__() ^ RANDOM
    if read_from_file:
        file = open('input.txt', 'r').readline().strip()[1:-1]
        fin = open(file, 'r')
        input = lambda : fin.readline().strip()
        output_file = open('output.txt', 'w')

        def fprint(*args, **kwargs):
            print(*args, **kwargs, file=output_file)
    if de:

        def debug(*args, **kwargs):
            print('\x1b[92m', end='')
            print(*args, **kwargs)
            print('\x1b[0m', end='')

class UnionFind:

    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, a):
        a = self.parent[a]
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            (self.parent[acopy], acopy) = (a, self.parent[acopy])
        return a

    def merge(self, a, b):
        (pa, pb) = (self.find(a), self.find(b))
        if pa == pb:
            return False
        self.parent[pb] = pa
        return True

class LCA:

    def __init__(self, n, parent, depth, val):
        self.n = n
        self.root = 0
        self.num = self.n.bit_length()
        self.depth = depth
        self.parent = [[-1] * self.n for i in range(self.num)]
        self.value = [[-1] * self.n for i in range(self.num)]
        self.parent[0] = parent
        self.value[0] = val
        for k in range(self.num - 1):
            for v in range(self.n):
                if self.parent[k][v] == -1:
                    self.parent[k + 1][v] = -1
                    self.value[k + 1][v] = self.value[k][v]
                else:
                    self.parent[k + 1][v] = self.parent[k][self.parent[k][v]]
                    self.value[k + 1][v] = max(self.value[k][v], self.value[k][self.parent[k][v]])

    def getLCA(self, u, v):
        res = 0
        if self.depth[u] > self.depth[v]:
            (u, v) = (v, u)
        for k in range(self.num):
            if self.depth[v] - self.depth[u] >> k & 1:
                if self.value[k][v] > res:
                    res = self.value[k][v]
                v = self.parent[k][v]
        if u == v:
            return res
        for k in reversed(range(self.num)):
            if self.parent[k][u] != self.parent[k][v]:
                if self.value[k][u] > res:
                    res = self.value[k][u]
                if self.value[k][v] > res:
                    res = self.value[k][v]
                u = self.parent[k][u]
                v = self.parent[k][v]
        if self.value[0][u] > res:
            res = self.value[0][u]
        if self.value[0][v] > res:
            res = self.value[0][v]
        return res

def main():
    (n, m, k, q) = MII()
    path = [[] for _ in range(n)]
    us = []
    vs = []
    ws = []
    for i in range(m):
        (u, v, w) = GMI()
        us.append(u)
        vs.append(v)
        ws.append(w + 1)
        path[u].append(i)
        path[v].append(i)
    dist = [-1] * n
    froms = [-1] * n
    for i in range(k):
        dist[i] = 0
        froms[i] = i
    hpq = list(range(k))
    while hpq:
        (d, u) = divmod(heappop(hpq), n)
        if dist[u] == d:
            for i in path[u]:
                v = vs[i] if us[i] == u else us[i]
                w = ws[i]
                if dist[v] == -1 or dist[v] > d + w:
                    dist[v] = d + w
                    froms[v] = froms[u]
                    heappush(hpq, dist[v] * n + v)
    new_us = []
    new_vs = []
    new_ws = []
    for i in range(m):
        new_us.append(froms[us[i]])
        new_vs.append(froms[vs[i]])
        new_ws.append(dist[us[i]] + dist[vs[i]] + ws[i])
    del us, vs, ws, path
    union = UnionFind(k)
    path = [[] for _ in range(k)]
    for i in sorted(range(m), key=lambda i: new_ws[i]):
        if union.merge(new_us[i], new_vs[i]):
            path[new_us[i]].append(i)
            path[new_vs[i]].append(i)
    parent = [-1] * k
    parent_weight = [0] * k
    depth = [0] * k
    stack = [0]
    while stack:
        u = stack.pop()
        for i in path[u]:
            v = new_vs[i] if new_us[i] == u else new_us[i]
            if parent[u] != v:
                parent[v] = u
                parent_weight[v] = new_ws[i]
                depth[v] = depth[u] + 1
                stack.append(v)
    lca = LCA(k, parent, depth, parent_weight)
    for _ in range(q):
        (u, v) = GMI()
        print(lca.getLCA(u, v))
    return
t = 1
for _ in range(t):
    main()