Long Way Home (Codeforces 1715E)
Tags: Greedy, divide and conquer

Stanley lives in a country that consists of $$$n$$$ cities (he lives in city $$$1$$$). There are bidirectional roads between some of the cities, and you know how long it takes to ride through each of them. Additionally, there is a flight between each pair of cities, the flight between cities $$$u$$$ and $$$v$$$ takes $$$(u - v)^2$$$ time.Stanley is quite afraid of flying because of watching "Sully: Miracle on the Hudson" recently, so he can take at most $$$k$$$ flights. Stanley wants to know the minimum time of a journey to each of the $$$n$$$ cities from the city $$$1$$$.

Input: In the first line of input there are three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \leq n \leq 10^{5}$$$, $$$1 \leq m \leq 10^{5}$$$, $$$1 \leq k \leq 20$$$) — the number of cities, the number of roads, and the maximal number of flights Stanley can take.The following $$$m$$$ lines describe the roads. Each contains three integers $$$u$$$, $$$v$$$, $$$w$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$, $$$1 \leq w \leq 10^{9}$$$) — the cities the road connects and the time it takes to ride through. Note that some pairs of cities may be connected by more than one road.

Output: Print $$$n$$$ integers, $$$i$$$-th of which is equal to the minimum time of traveling to city $$$i$$$.

Note: In the first sample, it takes no time to get to city 1; to get to city 2 it is possible to use a flight between 1 and 2, which will take 1 unit of time; to city 3 you can get via a road from city 1, which will take 1 unit of time. In the second sample, it also takes no time to get to city 1. To get to city 2 Stanley should use a flight between 1 and 2, which will take 1 unit of time. To get to city 3 Stanley can ride between cities 1 and 2, which will take 3 units of time, and then use a flight between 2 and 3. To get to city 4 Stanley should use a flight between 1 and 2, then take a ride from 2 to 4, which will take 5 units of time.

Sample Inputs:
3 1 2
1 3 1

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

2 1 1
2 1 893746473

5 5 2
2 1 33
1 5 93
5 3 48
2 3 21
4 2 1

Sample Outputs:
0 1 1

0 1 4 6

0 1

0 1 2 2 3

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, w, s) = ([], [], [0] * (n + 3))
    for _ in range(m):
        (u, v, w0) = map(int, input().split())
        s[u + 2] += 1
        s[v + 2] += 1
        x.append(u)
        x.append(v)
        w.append(w0)
    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]], W[s[j]]) = (x[i ^ 1], w[i // 2])
        s[j] += 1
    return (G, W, s)

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

def f(i, x):
    return a0[i] * x + b0[i]

def check(i, j, k):
    u = (a0[j] - a0[i]) * (b0[k] - b0[j])
    v = (b0[j] - b0[i]) * (a0[k] - a0[j])
    return True if u >= v else False

def add_line(a, b):
    if len(a0) and a0[-1] == a:
        b0[-1] = max(b0[-1], b)
    else:
        a0.append(a)
        b0.append(b)
    while len(a0) >= 3 and check(-3, -2, -1):
        (a0[-2], b0[-2]) = (a0[-1], b0[-1])
        a0.pop()
        b0.pop()
    return

def get_min(x):
    global i0
    i0 = min(i0, len(a0) - 1)
    while i0 < len(a0) - 1 and f(i0, x) >= f(i0 + 1, x):
        i0 += 1
    return f(i0, x)
(n, m, k) = map(int, input().split())
(G, W, s0) = make_graph(n, m)
inf = pow(10, 12) + 1
dist = [inf] * (n + 1)
dist[1] = 0
for _ in range(k):
    dijkstra()
    (a0, b0, i0) = ([], [], 0)
    mi = list(dist)
    for i in range(1, n + 1):
        add_line(-2 * i, dist[i] + i * i)
        mi[i] = min(mi[i], get_min(i) + i * i)
    (a0, b0, i0) = ([], [], 0)
    for i in range(n, 0, -1):
        j = n - i + 1
        add_line(-2 * j, dist[i] + j * j)
        mi[i] = min(mi[i], get_min(j) + j * j)
    dist = mi
dijkstra()
ans = dist[1:]
sys.stdout.write(' '.join(map(str, ans)))

Solution (Python):
from heapq import heappop, heapify, heappush
import io, os
read = io.BytesIO(os.read(0, os.fstat(0).st_size))
input = lambda : read.readline().decode().strip()

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

def GMI():
    return [int(x) - 1 for x in input().split()]
inf = 10 ** 18
(n, m, k) = MII()
us = [0] * m
vs = [0] * m
ws = [0] * m
path = [[] for _ in range(n)]
for i in range(m):
    (u, v, w) = GMI()
    us[i] = u
    vs[i] = v
    ws[i] = w + 1
    path[u].append(i)
    path[v].append(i)
dist = [inf] * n
dist[0] = 0
val = 1 << 17

def dijk():
    hpq = [w << 17 | i for (i, w) in enumerate(dist) if w < inf]
    heapify(hpq)
    while hpq:
        (d, u) = divmod(heappop(hpq), val)
        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] > dist[u] + w:
                    dist[v] = dist[u] + w
                    heappush(hpq, dist[v] << 17 | v)
stack = [0] * n

def relax(dist):

    def check(i1, i2, i3):
        return (dist[i2] + i2 * i2 - dist[i1] - i1 * i1) * (i3 - i2) >= (dist[i3] + i3 * i3 - dist[i2] - i2 * i2) * (i2 - i1)
    pr = 0
    for i in range(n):
        while pr > 1 and check(stack[pr - 2], stack[pr - 1], i):
            pr -= 1
        stack[pr] = i
        pr += 1

    def check_ans(pt):
        if pt < pr - 1 and (i - stack[pt]) * (i - stack[pt]) + dist[stack[pt]] >= (i - stack[pt + 1]) * (i - stack[pt + 1]) + dist[stack[pt + 1]]:
            return True
        return False
    ans = [0] * n
    pl = 0
    for i in range(n):
        while check_ans(pl):
            pl += 1
        ans[i] = (i - stack[pl]) * (i - stack[pl]) + dist[stack[pl]]
    return ans
dijk()
for _ in range(k):
    dist = relax(dist)
    dijk()
print(*dist)

Solution (Python):
import sys
input = sys.stdin.readline
from heapq import heappush, heappop
B = 10 ** 5 + 10

def dijkstra(G, dist, INF=10 ** 11):
    """"""
    N = len(dist)
    hp = []
    for i in range(N):
        heappush(hp, dist[i] * B + i)
    while hp:
        cv = heappop(hp)
        (c, v) = (cv // B, cv % B)
        if dist[v] < c:
            continue
        for (u, cost) in G[v]:
            if dist[v] + cost < dist[u]:
                dist[u] = dist[v] + cost
                heappush(hp, dist[u] * B + u)
    return dist
from collections import deque

class Convex_Hull_Trick:

    def __init__(self):
        self.deq = deque()

    def check(self, f1, f2, f3):
        return (f2[0] - f1[0]) * (f3[1] - f2[1]) >= (f2[1] - f1[1]) * (f3[0] - f2[0])

    def f(self, f1, x):
        return f1[0] * x + f1[1]

    def add_line(self, a, b):
        f1 = (a, b)
        while len(self.deq) >= 2 and self.check(self.deq[-2], self.deq[-1], f1):
            self.deq.pop()
        self.deq.append(f1)

    def query(self, x):
        while len(self.deq) >= 2 and self.f(self.deq[0], x) >= self.f(self.deq[1], x):
            self.deq.popleft()
        return self.f(self.deq[0], x)
(n, m, k) = map(int, input().split())
root = [[] for i in range(n + 2)]
for i in range(m):
    (a, b, c) = map(int, input().split())
    root[a].append((b, c))
    root[b].append((a, c))
dp = [10 ** 11] * (n + 1)
dp[1] = 0
dp = dijkstra(root, dp)
for iii in range(k):
    newdp = [10 ** 11] * (n + 1)
    cht = Convex_Hull_Trick()
    for i in range(1, n + 1):
        cht.add_line(-2 * i, dp[i] + i ** 2)
    for i in range(1, n + 1):
        newdp[i] = cht.query(i) + i ** 2
    dp = newdp[:]
    dp = dijkstra(root, dp)
print(*dp[1:])