Jog Around The Graph (Codeforces 1366F)
Tags: DP, geometry

You are given a simple weighted connected undirected graph, consisting of $$$n$$$ vertices and $$$m$$$ edges.A path in the graph of length $$$k$$$ is a sequence of $$$k+1$$$ vertices $$$v_1, v_2, \dots, v_{k+1}$$$ such that for each $$$i$$$ $$$(1 \le i \le k)$$$ the edge $$$(v_i, v_{i+1})$$$ is present in the graph. A path from some vertex $$$v$$$ also has vertex $$$v_1=v$$$. Note that edges and vertices are allowed to be included in the path multiple times.The weight of the path is the total weight of edges in it.For each $$$i$$$ from $$$1$$$ to $$$q$$$ consider a path from vertex $$$1$$$ of length $$$i$$$ of the maximum weight. What is the sum of weights of these $$$q$$$ paths?Answer can be quite large, so print it modulo $$$10^9+7$$$.

Input: The first line contains a three integers $$$n$$$, $$$m$$$, $$$q$$$ ($$$2 \le n \le 2000$$$; $$$n - 1 \le m \le 2000$$$; $$$m \le q \le 10^9$$$) — the number of vertices in the graph, the number of edges in the graph and the number of lengths that should be included in the answer.Each of the next $$$m$$$ lines contains a description of an edge: three integers $$$v$$$, $$$u$$$, $$$w$$$ ($$$1 \le v, u \le n$$$; $$$1 \le w \le 10^6$$$) — two vertices $$$v$$$ and $$$u$$$ are connected by an undirected edge with weight $$$w$$$. The graph contains no loops and no multiple edges. It is guaranteed that the given edges form a connected graph.

Output: Print a single integer — the sum of the weights of the paths from vertex $$$1$$$ of maximum weights of lengths $$$1, 2, \dots, q$$$ modulo $$$10^9+7$$$.

Note: Here is the graph for the first example:  Some maximum weight paths are:   length $$$1$$$: edges $$$(1, 7)$$$ — weight $$$3$$$;  length $$$2$$$: edges $$$(1, 2), (2, 3)$$$ — weight $$$1+10=11$$$;  length $$$3$$$: edges $$$(1, 5), (5, 6), (6, 4)$$$ — weight $$$2+7+15=24$$$;  length $$$4$$$: edges $$$(1, 5), (5, 6), (6, 4), (6, 4)$$$ — weight $$$2+7+15+15=39$$$;  $$$\dots$$$ So the answer is the sum of $$$25$$$ terms: $$$3+11+24+39+\dots$$$In the second example the maximum weight paths have weights $$$4$$$, $$$8$$$, $$$12$$$, $$$16$$$ and $$$20$$$.

Sample Inputs:
7 8 25
1 2 1
2 3 10
3 4 2
1 5 2
5 6 7
6 4 15
5 3 1
1 7 3

2 1 5
1 2 4

15 15 23
13 10 12
11 14 12
2 15 5
4 10 8
10 2 4
10 7 5
3 10 1
5 6 11
1 13 8
9 15 4
4 2 9
11 15 1
11 12 14
10 8 12
3 6 11

5 10 10000000
2 4 798
1 5 824
5 2 558
4 1 288
3 4 1890
3 1 134
2 3 1485
4 5 284
3 5 1025
1 2 649

Sample Outputs:
4361

60

3250

768500592

Solution (Python):
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)

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

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 binary_search(c1, c2):
    m = (c1 + c2 + 1) // 2
    while abs(c1 - c2) > 1:
        m = (c1 + c2 + 1) // 2
        if ok(m):
            c2 = m
        else:
            c1 = m
    m = max(m - 1, 0)
    while not ok(m):
        m += 1
    return m

def ok(m):
    return True if f(i, m) <= f(i + 1, m) or m >= inf else False
(n, m, q) = map(int, input().split())
mod = pow(10, 9) + 7
(G, W, s0) = make_graph(n, m)
dp = [-1] * (n + 1)
dp[1] = 0
ans = 0
for _ in range(m):
    dp0 = [-1] * (n + 1)
    for i in range(1, n + 1):
        if dp[i] == -1:
            continue
        dpi = dp[i]
        for v in range(s0[i], s0[i + 1]):
            (j, w) = (G[v], W[v])
            dp0[j] = max(dp0[j], dpi + w)
    dp = dp0
    ans += max(dp) % mod
(x, e) = ([0] * m, [])
l = max(n, m) + 1
for i in range(1, n + 1):
    for v in range(s0[i], s0[i + 1]):
        (j, w) = (G[v], W[v])
        if i < j:
            x[len(e)] = g(w, len(e))
            e.append(g(i, j))
(a0, b0) = ([], [])
for y in sorted(x, reverse=True):
    (w, i) = divmod(y, l)
    (u, v) = divmod(e[i], l)
    if max(dp[u], dp[v]) ^ -1:
        add_line(w, max(dp[u], dp[v]))
while len(a0) >= 2 and b0[-2] >= b0[-1]:
    a0.pop()
    b0.pop()
a0.reverse()
b0.reverse()
l = len(a0)
x = [0] * (l + 1)
inf = pow(10, 9) + 1
q -= m
for i in range(l - 1):
    x[i + 1] = min(binary_search(0, inf) - 1, q)
x[l] = q
inv2 = pow(2, mod - 2, mod)
for i in range(l):
    (u, v) = (x[i], x[i + 1])
    c = (v * (v + 1) - u * (u + 1)) % mod * inv2 % mod
    ans += a0[i] * c % mod + b0[i] * (v - u) % mod
ans %= mod
print(ans)

Solution (Python):
import sys

def rs():
    return sys.stdin.readline().rstrip()

def ri():
    return int(sys.stdin.readline())

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

def ws(s):
    sys.stdout.write(s + '\n')

def wi(n):
    sys.stdout.write(str(n) + '\n')

def wia(a):
    sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
MOD = 10 ** 9 + 7
INF = 100

def convex_hull_trick(K, M, integer=True):
    """"""
    if integer:
        intersect = lambda i, j: (M[j] - M[i]) // (K[i] - K[j])
    else:
        intersect = lambda i, j: (M[j] - M[i]) / (K[i] - K[j])
    assert len(K) == len(M)
    hull_i = []
    hull_x = []
    order = sorted(range(len(K)), key=K.__getitem__)
    for i in order:
        while True:
            if not hull_i:
                hull_i.append(i)
                break
            elif K[hull_i[-1]] == K[i]:
                if M[hull_i[-1]] >= M[i]:
                    break
                hull_i.pop()
                if hull_x:
                    hull_x.pop()
            else:
                x = intersect(i, hull_i[-1])
                if hull_x and x <= hull_x[-1]:
                    hull_i.pop()
                    hull_x.pop()
                else:
                    hull_i.append(i)
                    hull_x.append(x)
                    break
    return (hull_i, hull_x)

def nn2(n):
    return n * (n + 1) // 2

def solve(n, m, q, edges):
    dp = [[-INF] * (m + 1) for _ in range(n)]
    mk = [0] * (m + 1)
    dp[0][0] = 0
    for k in range(1, m + 1):
        for e in edges:
            if dp[e[0]][k - 1] == -INF:
                continue
            dp[e[1]][k] = max(dp[e[1]][k], dp[e[0]][k - 1] + e[2])
            mk[k] = max(mk[k], dp[e[1]][k])
    ans = sum(mk) % MOD
    if q > m:
        intersect = [dp[i][m] for i in range(n)]
        slope = [0] * n
        for e in edges:
            if e[2] > slope[e[0]]:
                slope[e[0]] = e[2]
        (hull_i, hull_x) = convex_hull_trick(slope, intersect)
        lt = 0
        for (i, j) in enumerate(hull_i):
            wt = intersect[j]
            w = slope[j]
            until = min(q if i == len(hull_x) else hull_x[i], q - m)
            if until <= 0:
                continue
            active = until - lt
            ans = (ans + active * wt) % MOD
            min_uses = lt
            max_uses = lt + active
            times = nn2(max_uses) - nn2(min_uses)
            ans = (ans + times * w) % MOD
            lt = until
            if lt == q - m:
                break
    return ans

def main():
    (n, m, q) = ria()
    e = []
    for _ in range(m):
        (u, v, w) = ria()
        u -= 1
        v -= 1
        e.append((u, v, w))
        e.append((v, u, w))
    wi(solve(n, m, q, e))
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
(n, m, q) = map(int, input().split())
MOD = 10 ** 9 + 7
edges = []
adj = [[] for _ in range(n)]
for i in range(m):
    (a, b, w) = map(int, input().split())
    a -= 1
    b -= 1
    edges.append((a, b, w))
    adj[a].append((b, w))
    adj[b].append((a, w))
INF = 10 ** 18
ans = 0
DP = [-INF] * n
DP[0] = 0
for plen in range(m):
    NDP = [-INF] * n
    for (a, b, w) in edges:
        NDP[b] = max(NDP[b], DP[a] + w)
        NDP[a] = max(NDP[a], DP[b] + w)
    DP = NDP
    ans = (ans + max(DP)) % MOD
''

def convex_hull_trick(K, M, integer=True):
    """"""
    if integer:
        intersect = lambda i, j: (M[j] - M[i]) // (K[i] - K[j])
    else:
        intersect = lambda i, j: (M[j] - M[i]) / (K[i] - K[j])
    assert len(K) == len(M)
    hull_i = []
    hull_x = []
    order = sorted(range(len(K)), key=K.__getitem__)
    for i in order:
        while True:
            if not hull_i:
                hull_i.append(i)
                break
            elif K[hull_i[-1]] == K[i]:
                if M[hull_i[-1]] >= M[i]:
                    break
                hull_i.pop()
                if hull_x:
                    hull_x.pop()
            else:
                x = intersect(i, hull_i[-1])
                if hull_x and x <= hull_x[-1]:
                    hull_i.pop()
                    hull_x.pop()
                else:
                    hull_i.append(i)
                    hull_x.append(x)
                    break
    return (hull_i, hull_x)
(slope, intersect) = ([], [])
for (a, b, w) in edges:
    i = max(a, b, key=lambda i: DP[i])
    assert DP[i] > 0
    slope.append(w)
    intersect.append(DP[i])
(hull_i, hull_x) = convex_hull_trick(slope, intersect)

def tri(x):
    return x * (x + 1) // 2
lt = 0
for (i, j) in enumerate(hull_i):
    (wt, w) = (intersect[j], slope[j])
    until = min(q if i == len(hull_x) else hull_x[i], q - m)
    if until <= 0:
        continue
    active = until - lt
    ans = (ans + active * wt) % MOD
    min_uses = lt
    max_uses = lt + active
    times = tri(max_uses) - tri(min_uses)
    ans = (ans + times * w) % MOD
    lt = until
    if lt == q - m:
        break
print(ans)