Pokémon Arena (Codeforces 1937E)
Tags: Others, 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):
from collections import *
from itertools import *
from functools import *
from heapq import *
import sys, math
input = sys.stdin.readline
INF = 1 << 60

def dijkstra(s, e):
    N = len(e)
    dist = [INF] * N
    dist[s] = 0
    h = []
    heappush(h, s)
    while h:
        (nw, v) = divmod(heappop(h), N)
        if dist[v] != nw:
            continue
        for (iv, ic) in e[v]:
            nc = ic + nw
            if nc < dist[iv]:
                dist[iv] = nc
                heappush(h, nc * N + iv)
    return dist

def answer():
    (N, M) = map(int, input().split())
    e = [[] for _ in range(N * (M + 1))]
    C = list(map(int, input().split()))
    A = [list(map(int, input().split())) for _ in range(N)]
    for i in range(M):
        X = [(A[j][i], j) for j in range(N)]
        X.sort(reverse=True)
        for j in range(N):
            _j = j + (i + 1) * N
            e[j].append((_j, C[j]))
            e[_j].append((j, 0))
        for j in range(N - 1):
            (vi, idx) = X[j]
            (vj, jdx) = X[j + 1]
            _idx = idx + (i + 1) * N
            _jdx = jdx + (i + 1) * N
            e[_idx].append((_jdx, 0))
            e[_jdx].append((_idx, vi - vj))
    D = dijkstra(N - 1, e)
    print(D[0])
for _ in range(int(input())):
    answer()

Solution (Python):
import math
import sys
from heapq import *
input = lambda : sys.stdin.readline().rstrip()
sint = lambda : int(input())
mint = lambda : map(int, input().split())
ints = lambda : list(map(int, input().split()))

def solve() -> None:
    (n, m) = mint()
    cost = ints()
    g = [[] for _ in range(n * (m + 1))]
    attr = []
    for i in range(n):
        attr.append(ints())
        for j in range(m):
            atti = (j + 1) * n + i
            g[i].append((atti, cost[i]))
            g[atti].append((i, 0))
    idx = list(range(n))
    for j in range(m):
        idx.sort(key=lambda x: attr[x][j])
        for i in range(1, n):
            x = (j + 1) * n + idx[i - 1]
            y = (j + 1) * n + idx[i]
            g[x].append((y, attr[idx[i]][j] - attr[idx[i - 1]][j]))
            g[y].append((x, 0))
    dis = [math.inf] * (n * (m + 1))
    dis[n - 1] = 0
    h = [(0, n - 1)]
    while h:
        (d, x) = heappop(h)
        if d > dis[x]:
            continue
        for (y, w) in g[x]:
            new_d = d + w
            if new_d < dis[y]:
                dis[y] = new_d
                heappush(h, (new_d, y))
    print(dis[0])
for _ in range(int(input())):
    solve()

Solution (Python):
from collections import *
from itertools import *
from functools import *
from heapq import *
import sys, math
input = sys.stdin.readline
INF = 1 << 60

def dijkstra(s, e):
    N = len(e)
    dist = [INF] * N
    dist[s] = 0
    h = []
    heappush(h, s)
    while h:
        (nw, v) = divmod(heappop(h), N)
        if dist[v] != nw:
            continue
        for (iv, ic) in e[v]:
            nc = ic + nw
            if nc < dist[iv]:
                dist[iv] = nc
                heappush(h, nc * N + iv)
    return dist

def answer():
    (N, M) = map(int, input().split())
    e = [[] for _ in range(N * (M + 1))]
    C = list(map(int, input().split()))
    A = [list(map(int, input().split())) for _ in range(N)]
    for i in range(M):
        X = [(A[j][i], j) for j in range(N)]
        X.sort(reverse=True)
        for j in range(N):
            _j = j + (i + 1) * N
            e[j].append((_j, C[j]))
            e[_j].append((j, 0))
        for j in range(N - 1):
            (vi, idx) = X[j]
            (vj, jdx) = X[j + 1]
            _idx = idx + (i + 1) * N
            _jdx = jdx + (i + 1) * N
            e[_idx].append((_jdx, 0))
            e[_jdx].append((_idx, vi - vj))
    D = dijkstra(N - 1, e)
    print(D[0])
for _ in range(int(input())):
    answer()