Pokémon Arena (Codeforces 1936C)
Tags: Greedy, shortest paths

You are at a dueling arena. You also possess $$$n$$$ Pokémons. Initially, only the $$$1$$$-st Pokémon is standing in the arena.Each Pokémon has $$$m$$$ attributes. The $$$j$$$-th attribute of the $$$i$$$-th Pokémon is $$$a_{i,j}$$$. Each Pokémon also has a cost to be hired: the $$$i$$$-th Pokémon's cost is $$$c_i$$$.You want to have the $$$n$$$-th Pokémon stand in the arena. To do that, you can perform the following two types of operations any number of times in any order:   Choose three integers $$$i$$$, $$$j$$$, $$$k$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$, $$$k > 0$$$), increase $$$a_{i,j}$$$ by $$$k$$$ permanently. The cost of this operation is $$$k$$$.  Choose two integers $$$i$$$, $$$j$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$) and hire the $$$i$$$-th Pokémon to duel with the current Pokémon in the arena based on the $$$j$$$-th attribute. The $$$i$$$-th Pokémon will win if $$$a_{i,j}$$$ is greater than or equal to the $$$j$$$-th attribute of the current Pokémon in the arena (otherwise, it will lose). After the duel, only the winner will stand in the arena. The cost of this operation is $$$c_i$$$. Find the minimum cost you need to pay to have the $$$n$$$-th Pokémon stand in the arena.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 4 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$, $$$2 \leq n \cdot m \leq 4 \cdot 10^5$$$).The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$).The $$$i$$$-th of the following $$$n$$$ lines contains $$$m$$$ integers $$$a_{i,1}, a_{i,2}, \ldots, a_{i,m}$$$ ($$$1 \le a_{i,j} \le 10^9$$$).It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output: For each test case, output the minimum cost to make the $$$n$$$-th Pokémon stand in the arena.

Note: In the first test case, the attribute array of the $$$1$$$-st Pokémon (which is standing in the arena initially) is $$$[2,9,9]$$$.In the first operation, you can choose $$$i=3$$$, $$$j=1$$$, $$$k=1$$$, and increase $$$a_{3,1}$$$ by $$$1$$$ permanently. Now the attribute array of the $$$3$$$-rd Pokémon is $$$[2,2,1]$$$. The cost of this operation is $$$k = 1$$$.In the second operation, you can choose $$$i=3$$$, $$$j=1$$$, and hire the $$$3$$$-rd Pokémon to duel with the current Pokémon in the arena based on the $$$1$$$-st attribute. Since $$$a_{i,j}=a_{3,1}=2 \ge 2=a_{1,1}$$$, the $$$3$$$-rd Pokémon will win. The cost of this operation is $$$c_3 = 1$$$.Thus, we have made the $$$3$$$-rd Pokémon stand in the arena within the cost of $$$2$$$. It can be proven that $$$2$$$ is minimum possible.In the second test case, the attribute array of the $$$1$$$-st Pokémon in the arena is $$$[9,9,9]$$$.In the first operation, you can choose $$$i=2$$$, $$$j=3$$$, $$$k=2$$$, and increase $$$a_{2,3}$$$ by $$$2$$$ permanently. Now the attribute array of the $$$2$$$-nd Pokémon is $$$[6,1,9]$$$. The cost of this operation is $$$k = 2$$$.In the second operation, you can choose $$$i=2$$$, $$$j=3$$$, and hire the $$$2$$$-nd Pokémon to duel with the current Pokémon in the arena based on the $$$3$$$-rd attribute. Since $$$a_{i,j}=a_{2,3}=9 \ge 9=a_{1,3}$$$, the $$$2$$$-nd Pokémon will win. The cost of this operation is $$$c_2 = 3$$$.In the third operation, you can choose $$$i=3$$$, $$$j=2$$$, and hire the $$$3$$$-rd Pokémon to duel with the current Pokémon in the arena based on the $$$2$$$-nd attribute. Since $$$a_{i,j}=a_{1,2}=2 \ge 1=a_{2,2}$$$, the $$$3$$$-rd Pokémon can win. The cost of this operation is $$$c_3 = 1$$$.Thus, we have made the $$$3$$$-rd Pokémon stand in the arena within the cost of $$$6$$$. It can be proven that $$$6$$$ is minimum possible.

Sample Inputs:
4
3 3
2 3 1
2 9 9
6 1 7
1 2 1
3 3
2 3 1
9 9 9
6 1 7
1 2 1
4 2
2 8 3 5
18 24
17 10
1 10
1 1
6 3
21412674 3212925 172015806 250849370 306960171 333018900
950000001 950000001 950000001
821757276 783362401 760000001
570000001 700246226 600757652
380000001 423513575 474035234
315201473 300580025 287023445
1 1 1

Sample Outputs:
2
6
17
1224474550

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

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

def h(u, v):
    return u << 20 ^ v

def make_graph(n, m):
    s = [0] * (n + 3)
    for i in x:
        s[i + 2] += 1
    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]
        s[j] += 1
    return (G, W, s)

def dijkstra(s, g):
    dist = [inf] * (n * m + n)
    dist[s] = 0
    visit = [0] * (n * m + n)
    p = []
    heapq.heappush(p, h(dist[s], s))
    while p:
        z = heapq.heappop(p)
        (d, u) = (z >> 20, z & 1048575)
        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, h(dist[v], v))
    return dist[g]
t = int(input())
ans = []
inf = pow(10, 18) + 1
for _ in range(t):
    (n, m) = map(int, input().split())
    c = list(map(int, input().split()))
    a = [0] * (n * m)
    for i in range(n):
        a0 = list(map(int, input().split()))
        for j in range(m):
            a[f(i, j)] = a0[j]
    (x, y) = ([], [])
    for j in range(m):
        z = [h(a[f(i, j)], f(i, j)) for i in range(n)]
        z.sort()
        for i in range(n - 1):
            (u, v) = (z[i] & 1048575, z[i + 1] & 1048575)
            x.append(u)
            x.append(v)
            y.append(0)
            y.append(a[v] - a[u])
    for i in range(n):
        for j in range(m):
            x.append(n * m + i)
            x.append(f(i, j))
            y.append(0)
            y.append(c[i])
    (G, W, s0) = make_graph(n * m + n, len(x) >> 1)
    ans0 = dijkstra(n * m, n * m + n - 1)
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

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

def main(t):
    (m, n) = map(int, input().split())
    cost = list(map(int, input().split()))
    data = []
    for _ in range(m):
        data.append(list(map(int, input().split())))
    tot = m * n
    neigh = [[] for _ in range(2 * tot)]
    for index in range(m * n):
        i = index // n
        j = index % n
        neigh[index].append((index + tot, cost[i]))
        neigh[index + tot].append((index, 0))
        if j != n - 1:
            neigh[index].append((index + 1, 0))
            neigh[index + 1].append((index, 0))
    for j in range(n):
        temp = []
        for i in range(m):
            temp.append((data[i][j], i))
        temp.sort()
        for i in range(m - 1):
            index = temp[i][1] * n + j + tot
            nextindex = temp[i + 1][1] * n + j + tot
            neigh[index].append((nextindex, temp[i + 1][0] - temp[i][0]))
            neigh[nextindex].append((index, 0))
    distance = [float('inf')] * (2 * tot)
    temp = [float('inf')] * (2 * tot)
    heap = []
    heapq.heappush(heap, (0, (m - 1) * n))
    temp[(m - 1) * n] = 0
    while heap:
        ele = heapq.heappop(heap)
        (d, index) = ele
        if distance[index] <= d:
            continue
        distance[index] = d
        for (nextindex, nextd) in neigh[index]:
            if temp[nextindex] <= d + nextd:
                continue
            temp[nextindex] = d + nextd
            heapq.heappush(heap, (d + nextd, nextindex))
    ans = distance[0]
    print(ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

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

def main(t):
    (m, n) = map(int, input().split())
    cost = list(map(int, input().split()))
    data = []
    for _ in range(m):
        data.append(list(map(int, input().split())))
    tot = m * n
    neigh = [[] for _ in range(2 * tot)]
    for index in range(m * n):
        i = index // n
        j = index % n
        neigh[index].append((index + tot, cost[i]))
        neigh[index + tot].append((index, 0))
        if j != n - 1:
            neigh[index].append((index + 1, 0))
            neigh[index + 1].append((index, 0))
    for j in range(n):
        temp = []
        for i in range(m):
            temp.append((data[i][j], i))
        temp.sort()
        for i in range(m - 1):
            index = temp[i][1] * n + j + tot
            nextindex = temp[i + 1][1] * n + j + tot
            neigh[index].append((nextindex, temp[i + 1][0] - temp[i][0]))
            neigh[nextindex].append((index, 0))
    distance = [float('inf')] * (2 * tot)
    heap = []
    heapq.heappush(heap, (0, (m - 1) * n))
    while heap:
        ele = heapq.heappop(heap)
        (d, index) = ele
        if distance[index] <= d:
            continue
        distance[index] = d
        for (nextindex, nextd) in neigh[index]:
            if distance[nextindex] <= d + nextd:
                continue
            heapq.heappush(heap, (d + nextd, nextindex))
    ans = distance[0]
    print(ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1