Problem:


Score : 400 points

Problem Statement

Joisino the magical girl has decided to turn every single digit that exists on this world into 1.

Rewriting a digit i with j (0≤i,j≤9) costs c_{i,j} MP (Magic Points).

She is now standing before a wall. The wall is divided into HW squares in H rows and W columns, and at least one square contains a digit between 0 and 9 (inclusive).

You are given A_{i,j} that describes the square at the i-th row from the top and j-th column from the left, as follows:

If A_{i,j}≠-1, the square contains a digit A_{i,j}.

If A_{i,j}=-1, the square does not contain a digit.

Find the minimum total amount of MP required to turn every digit on this wall into 1 in the end.

Constraints

1≤H,W≤200

1≤c_{i,j}≤10^3 (i≠j)

c_{i,j}=0 (i=j)

-1≤A_{i,j}≤9

All input values are integers.

There is at least one digit on the wall.

Input

Input is given from Standard Input in the following format:

H W
c_{0,0} ... c_{0,9}
:
c_{9,0} ... c_{9,9}
A_{1,1} ... A_{1,W}
:
A_{H,1} ... A_{H,W}

Output

Print the minimum total amount of MP required to turn every digit on the wall into 1 in the end.

Sample Input 1

2 4
0 9 9 9 9 9 9 9 9 9
9 0 9 9 9 9 9 9 9 9
9 9 0 9 9 9 9 9 9 9
9 9 9 0 9 9 9 9 9 9
9 9 9 9 0 9 9 9 9 2
9 9 9 9 9 0 9 9 9 9
9 9 9 9 9 9 0 9 9 9
9 9 9 9 9 9 9 0 9 9
9 9 9 9 2 9 9 9 0 9
9 2 9 9 9 9 9 9 9 0
-1 -1 -1 -1
8 1 1 8

Sample Output 1

12

To turn a single 8 into 1, it is optimal to first turn 8 into 4, then turn 4 into 9, and finally turn 9 into 1, costing 6 MP.

The wall contains two 8s, so the minimum total MP required is 6×2=12.

Sample Input 2

5 5
0 999 999 999 999 999 999 999 999 999
999 0 999 999 999 999 999 999 999 999
999 999 0 999 999 999 999 999 999 999
999 999 999 0 999 999 999 999 999 999
999 999 999 999 0 999 999 999 999 999
999 999 999 999 999 0 999 999 999 999
999 999 999 999 999 999 0 999 999 999
999 999 999 999 999 999 999 0 999 999
999 999 999 999 999 999 999 999 0 999
999 999 999 999 999 999 999 999 999 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Sample Output 2

0

Note that she may not need to change any digit.

Sample Input 3

3 5
0 4 3 6 2 7 2 5 3 3
4 0 5 3 7 5 3 7 2 7
5 7 0 7 2 9 3 2 9 1
3 6 2 0 2 4 6 4 2 3
3 5 7 4 0 6 9 7 6 7
9 8 5 2 2 0 4 7 6 5
5 4 6 3 2 3 0 5 4 3
3 6 2 3 4 2 4 0 8 9
4 6 5 4 3 5 3 2 0 8
2 1 3 4 5 7 8 6 4 0
3 5 2 6 1
2 5 3 2 1
6 9 2 5 6

Sample Output 3

47



Sample input:
2 4
0 9 9 9 9 9 9 9 9 9
9 0 9 9 9 9 9 9 9 9
9 9 0 9 9 9 9 9 9 9
9 9 9 0 9 9 9 9 9 9
9 9 9 9 0 9 9 9 9 2
9 9 9 9 9 0 9 9 9 9
9 9 9 9 9 9 0 9 9 9
9 9 9 9 9 9 9 0 9 9
9 9 9 9 2 9 9 9 0 9
9 2 9 9 9 9 9 9 9 0
-1 -1 -1 -1
8 1 1 8


Sample output:
12

Submission status: Accepted

Solution code:
def search_min_cost(nums, prev_num, min_cost, cost, c):
    _last_min_cost = min_cost
    if len(nums) != 0:
        _min_cost = cost + c[prev_num][1]
        if min_cost < _min_cost:
            _min_cost = min_cost
        for i in nums:
            _nums = nums[:]
            _nums.remove(i)
            next_cost = cost + c[prev_num][i]
            if _min_cost <= next_cost:
                if _min_cost < _last_min_cost:
                    _last_min_cost = _min_cost
            else:
                '''
                if prev_num == 8:
                    print(_nums, i, _min_cost, next_cost)
                if prev_num == 4 and i == 9:
                    print(_nums, i, _min_cost, next_cost)
                '''
                m = search_min_cost(
                    _nums, i, _min_cost, next_cost, c)
                if m < _last_min_cost:
                    _last_min_cost = m
    else:
        m = cost + c[prev_num][1]
        if m < _last_min_cost:
            _last_min_cost = m
    return _last_min_cost


H, W = map(int, input().split())
# c[y][x]: y行目、x文字目
c = [list(map(int, input().split())) for _ in range(10)]
# A[y][x]: y行目、x文字目
A = [list(map(int, input().split())) for _ in range(H)]
min_cost_map = {}
min_cost_map[1] = 0

nums = [0, 2, 3, 4, 5, 6, 7, 8, 9]
for i in nums:
    _nums = nums[:]
    _nums.remove(i)
    min_cost_map[i] = search_min_cost(_nums, i, 1001, 0, c)
# print(min_cost_map)
cost = 0
for i in range(H):
    for j in range(W):
        n = A[i][j]
        if n != -1:
            cost += min_cost_map[n]
print(cost)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
C = [list(map(int, input().split())) for i in range(10)]

for k in range(10):
    for i in range(10):
        for j in range(10):
            C[i][j] = min(C[i][j], C[i][k] + C[k][j])

ans = 0
for h in range(H):
    A = list(map(int, input().split()))
    for a in A:
        if a >= 0:
            ans += C[a][1]

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]

a = [list(map(int, input().split())) for _ in range(h)]

#for p in c: print(p)
#for p in a: print(a)

n = 10
dp = [[1000 for _ in range(n)] for _ in range(n)]

for i in range(n):
    dp[0][i] = c[i][1]

#for p in dp: print(p)

for i in range(1, n):
    for j in range(n):
        for k in range(n):
            dp[i][j] = min(dp[i][j], c[j][k] + dp[i - 1][k])

#for p in dp: print(p)

ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] >= 0:
            ans += dp[n - 1][a[i][j]]

print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
c = [list(map(int,input().split())) for i in range(10)]
import queue



d = c.copy()
for k in range(10):
    for i in range(10):
        for j in range(10):
            if d[i][j] > d[i][k]+d[k][j]:
                d[i][j] = d[i][k]+d[k][j]

cost = []
for i in range(10):
    cost.append(d[i][1])

ans = 0
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        if A[j] != -1:
            ans += cost[A[j]]
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
c = [list(map(int,input().split())) for i in range(10)]
import queue

def dist(i):
    res = c[i][1]
    que = queue.Queue()
    path = []
    for j in range(10):
        if j != i and j != 1:
            path.append(j)
    for j in range(10):
        if j != 1 and j != i and c[i][j] < res:
            jpath = path.copy()
            jpath.pop(jpath.index(j))
            que.put((j,c[i][j],jpath))
    while que.qsize():
        j,cost,path = que.get()
        if cost + c[j][1] < res:
            res = cost + c[j][1]
        for k in path:
            if k != 1 and cost+c[j][k] < res:
                kpath = path.copy()
                kpath.pop(kpath.index(k))
                que.put((k,cost+c[j][k],kpath))
    return res

cost = []
for i in range(10):
    cost.append(dist(i))

ans = 0
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        if A[j] != -1:
            ans += cost[A[j]]
print(ans)

Submission status: Accepted

Solution code:

c = []

def main():
    buf = input()
    buflist = buf.split()
    H = int(buflist[0])
    W = int(buflist[1])
    global c
    for i in range(10):
        buf = input()
        buflist = buf.split()
        c.append(list(map(int, buflist)))
    A = []
    for i in range(H):
        buf = input()
        buflist = buf.split()
        A.append(list(map(int, buflist)))
    cost_list = []
    for i in range(10):
        nlist = []
        for j in range(10):
            if j != 1:
                nlist.append(j)
        cost_list.append(min_cost_of(i, 1, 1, nlist, 0))
    number_count = []
    for i in range(10):
        i_count = 0
        for j in range(H):
            for k in range(W):
                if A[j][k] == i:
                    i_count += 1
        number_count.append(i_count)
    mp_needed = 0
    for i in range(10):
        mp_needed += cost_list[i] * number_count[i]
    print(mp_needed)

def min_cost_of(s, d, t, nlist, cost):
    if s == d or s == t:
        return cost
    else:
        minimum = c[s][d]
        for i in nlist:
            rlist = list(nlist)
            rlist.remove(i)
            result = min_cost_of(s, d, i, rlist, cost + c[i][t])
            if result < minimum:
                minimum = result
        return minimum

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
c=[list(map(int,input().split())) for _ in range(10)]
a=[list(map(int,input().split())) for _ in range(h)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])
ans=0
for i in range(h):
    for j in range(w):
        ans+=c[abs(a[i][j])][1]
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
INF = 10 ** 4
c = [[int(i) for i in input().split()] for _ in range(10)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j] = min(c[i][j], c[i][k] + c[k][j])

ans = 0
for _ in range(H):
    for a in map(int, input().split()):
        if a != -1:
            ans += c[a][1]
print(ans)

Submission status: Accepted

Solution code:
def main():

    S = list(input())
    checklist = [0 for i in range(26)]
    for i in S:
        checklist[ord(i) - ord("a")] += 1
    ans = True

    for i in checklist:
        if i > 1:
            ans = False

    if not ans:
        print(-1)
        return 0
    else:
        ans = False
        for i in range(len(checklist)):
            if checklist[i] == 0:
                for i in S:
                    print(i, end="")
                print(chr(i + ord("a")), end = "")
                print()
                ans = True
                break

        if not ans:
            new_S = []
            for i in S:
                new_S.append(ord(i))

            for i in range(len(new_S) - 1):
                if new_S[i] > new_S[i + 1]:
                    for j in range(i - 1):
                        print(S[j], end = "")
                    print(chr(new_S[i - 1] + 1), end = "")
                    print()
                    ans = True
                    break

            if not ans:
                print(-1)
#main()

def ABC069D():

    H, W = map(int, input().split())
    N = int(input())
    a = list(map(int, input().split()))
    ans = []
    for i in range(N):
        for j in range(a[i]):
            ans.append(i + 1)
    printlist = [[0 for i in range(W)] for j in range(H)]
    k = 0
    for i in range(H):
        for j in range(W):
            printlist[i][j] = ans[k]
            k += 1
        if i % 2 != 0:
            printlist[i] = printlist[i][::-1]

    for i in range(H):
        for j in range(W):
            print(printlist[i][j], end = "")
            if j != W:
                print(" ", end = "")
        print()
    print()
#ABC069D()

import math
def cc(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def ABC057D():

    N, A, B = map(int, input().split())
    v = list(map(int, input().split()))
    v = sorted(v)[::-1]

    anslist = []
    for i in range(A, B + 1):

        anslist.append([sum(v[0:i]) / i, i, v[i - 1]])
    anslist.sort()
    anslist = anslist[::-1]
    ans = anslist[0][0]
    key = anslist[0][2]
    long = anslist[0][1]
    print(ans)
    for i in range(1, len(anslist)):
        if anslist[i][0] == anslist[i - 1][0]:
            ans = anslist[i][0]
            key = anslist[i][2]
            long = anslist[i][1]
        else:
            break
    #print(anslist)
    #print(ans, key, long)
    cnt = 0
    for i in v:
        if i == key:
            cnt += 1

    c = 0
    for i in v[:long]:
        #print(i)
        if i == key:
            c += 1
    #print(c, long)
    ans = 0
    if c == long:
        for i in range(A,  min(B + 1, cnt + 1)):
            ans += cc(cnt, i)
    else:
        ans = cc(cnt, c)
    #print(anslist)
    #print(cnt, c, long)
    print(ans)
#ABC057D()

def ABC104D():
    S = list(input())
    A_cnt = 0
    B_cnt = 0
    C_cnt = 0
    Q_cnt = 0
    ans = 0
    for i in S:
        if i == "A":
            A_cnt += 1
        elif i == "B":
            B_cnt += 1
        elif i == "C":
            C_cnt += 1
        else:
            Q_cnt += 1
    for i in range(Q_cnt + 1):
        for j in range(Q_cnt - i + 1):
            k = Q_cnt - i - j
            if A_cnt + i > 0 and B_cnt + j > 0 and C_cnt + k > 0:
                f_i = math.factorial(i)
                f_j = math.factorial(j)
                f_k = math.factorial(k)
                if f_i == 0:
                    f_i = 1
                if f_j == 0:
                    f_j = 1
                if f_k == 0:
                    f_k = 1
                ans += (A_cnt + i) * (B_cnt + j) * (C_cnt + k) * math.factorial(Q_cnt) // f_i // f_j // f_k
                print(ans, i, j, k, A_cnt + i, B_cnt + j, C_cnt + k)
                print(math.factorial(Q_cnt), f_i, f_j, f_k)
    print(ans)
#ABC104D()

def ARC082D():
    N = int(input())
    p = list(map(int, input().split()))
    cnt = 0
    if p[N - 1] == N:
        #print(p[N - 1], N)
        p[-2], p[-1] = p[-1], p[-2]
        cnt += 1

    for i in range(N - 1):
        if p[i] == i + 1:
            p[i], p[i + 1] = p[i + 1], p[i]
            cnt += 1
    print(cnt)
#ARC082D()

from queue import Queue
def ABC070D():
    N = int(input())
    a, b, c =map(int, input().split())
    Q, K = map(int, input().split())
    xy = [list(map(int, input().split())) for i in range(Q)]
    x = [[] for i in range(N)]
    for i, j in xy:
        x[i - 1].append(j - 1)
        x[j - 1].append(i - 1)

    q = Queue()
    visited = [0 for i in range(N)]

def ABC076D():
    N = int(input())
    t = list(map(int, input().split()))
    v = list(map(int, input().split()))
    speed_lim = [0]
    speed_list = [0 for i in range(sum(t) + 1)]
    for i in range(N):
        for j in range(t[i]):
            speed_lim.append(v[i])
    print(speed_lim)
    for i in range(1, sum(t) + 1):
        speed_list[i] = speed_list[i - 1] + 1
        if speed_list[i] > speed_lim[i]:
            speed_list[i] = speed_lim[i]
    print(speed_list)
    speed_list[-1] = 0
    for i in range(sum(t) - 1, -1, -1):
        speed_list[i] = min(speed_list[i + 1] + 1, speed_list[i])
        if speed_list[i] > speed_lim[i + 1]:
            speed_list[i] = speed_lim[i + 1]
    print(speed_list)
    ans = 0
    for i in speed_list:
        ans += i

    print(ans)
#ABC076D()

def ABC085D():
    N, H = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(N)]
    a = []
    b = []
    for i, j in ab:
        a.append(i)
        b.append(j)
    a.sort()
    b.sort()
    a = a[::-1]
    b = b[::-1]
    damage = 0
    cnt = 0
    for i in b:
        if i < a[0]:
            break
        damage += i
        cnt += 1
        if damage >= H:
            break
    key = 0
    if damage < H:
        key = (H - damage) / a[0]
        if int(key) != key:
            key += 1
        key = int(key)

    cnt += key

    print(cnt)
#ABC085D()

def ARC068D():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    count_list = []
    cnt = 1
    #print(A)
    for i in range(1, N):
        if A[i] == A[i - 1]:
            cnt += 1
        else:
            count_list.append(cnt)
            cnt = 1
    count_list.append(cnt)
    ans_cnt = 0
    #print(count_list)
    for i in range(len(count_list)):
        if count_list[i] > 2:
            ans_cnt += (count_list[i] % 2) - 1
            count_list[i] %= 2
            if count_list[i] == 0:
                count_list[i] = 2
    #print(ans_cnt)
    count_list = sorted(count_list)[::-1]
    for i in range(len(count_list) - 1):
        if count_list[i] == 2 and count_list[i + 1] == 2:
            ans_cnt += 1
            count_list[i] = 1
            count_list[i + 1] = 1
    count_list = sorted(count_list)[::-1]
    if count_list[0] == 2:
        count_list[0] = 0
    #print(ans_cnt)
    #print(count_list)
    print(sum(count_list))
#ARC068D()

def ARC073D():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for i in range(N)]
    wv.sort()
    count_list = []
    cnt = 1
    weight_list = []
    s = 0
    g = 0
    for i in range(N - 1):
        if wv[i][0] != wv[i + 1][0]:
            g = i
            count_list.append(cnt)
            weight_list.append([wv[i][0], s, g, cnt])
            s = i + 1
            g = i + 1
            cnt = 1
        else:
            g = i
            cnt += 1

    count_list.append(cnt)
    weight_list.append([wv[-1][0], s, g, cnt])
    print(weight_list)
    wl = []
    for i in weight_list:
        this_weight = i[0]
        this_list = []
        for j in wv[i[1]:i[2] + 1]:
            this_list.append(j[1])
        this_list = sorted(this_list)[::-1]
        print(this_list)
        wl.append([this_weight, this_list])

def ARC081D():
    pattern = []
    N = int(input())
    S1 = list(input())
    S2 = list(input())
    i = 0
    while i < N:
        if S1[i] == S2[i]:
            pattern.append("X")
        else:
            pattern.append("Y")
            i += 1
        i += 1
    ans_list = []
    for i in range(len(pattern)):
        if i == 0:
            if pattern[i] == "X":
                ans_list.append(3)
            else:
                ans_list.append(6)
        else:
            if pattern[i] == "X":
                if pattern[i - 1] == "X":
                    ans_list.append(2)
                else:
                    ans_list.append(1)
            elif pattern[i] == "Y":
                if pattern[i - 1] == "X":
                    ans_list.append(2)
                elif pattern[i - 1] == "Y":
                    ans_list.append(3)
    #print(pattern)
    #print(ans_list)
    ans = 1
    for i in ans_list:
        ans *= i
    print(ans % (1000000007))
#ARC081D()

def ARC090D():
    N, M = map(int, input().split())
    LRD = [list(map(int, input().split())) for i in range(M)]
    L = []
    R = []
    D = []
    LRD.sort()
    root = [[] for i in range(N)]
    for i, j, k in LRD:
        L.append(i)
        R.append(j)
        D.append(k)
        root[i - 1].append(j - 1)
    print(root)
#ARC090D()

def ABC073D():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    ABC = [list(map(int, input().split())) for i in range(M)]
    root = [[1000000000 for i in range(N)] for j in range(N)]
    for i, j, k in ABC:
        root[i - 1][j - 1] = k
        root[j - 1][i - 1] = k

    import itertools
    def kumiawase(list_name):  # list_name(リスト)のすべての並び替え
        return itertools.permutations(list_name)

    #for i in range(N):
     #   for j in range(N):
      #      for k in range(N):
       #         if root[i][j] > root[i][k] + root[k][j]:
        #            root[i][j] = root[i][k] + root[k][j]

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if root[N - i - 1][N - j - 1] > root[N - i - 1][N - k - 1] + root[N - k - 1][N - j - 1]:
                    root[N - i - 1][N - j - 1] = root[N - i - 1][N - k - 1] + root[N - k- 1][N - j - 1]

    a = kumiawase(r)
    ans = float("inf")
    for i in a:
        key = 0
        for j in range(len(i) - 1):
            key += root[i[j] - 1][i[j + 1] - 1]
        if ans > key:
            ans = int(key)
    #print(root)
    print(ans)
#ABC073D()

def ARC061D():
    H, W, N = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(N)]
    ab.sort()
    tmp_list = []
    ans_list = [0 for i in range(10)]
    for x, y, in ab:
        for i in range(x - 3, x):
            for j in range(y - 3, y):
                if 0 <= i < H - 2 and 0 <= j < W - 2:
                    #print(x, y, i, j)
                    tmp_list.append([i, j])
    #print(tmp_list)
    tmp_list.sort()
    temp = 1
    #print(tmp_list)
    cnt = 0
    for i in range(1, len(tmp_list) + 1):
        if i != len(tmp_list):
            if tmp_list[i] == tmp_list[i - 1]:
                temp += 1
            else:
                ans_list[temp] += 1
                temp = 1
                cnt += 1
        else:
            ans_list[temp] += 1
            cnt += 1
    #print(ans_list)

    key = 0
    for i in range(len(ans_list)):
        key += i * ans_list[i]
    ans_list[0] = (H - 2) * (W - 2) - cnt
    #print(key)
    #print((H - 2) * (W - 2) - key)

    for i in range(10):
        print(ans_list[i])
#ARC061D()

from scipy.sparse import csgraph
#root = csgraph.floyd_warshall(root)

def ABC079D():
    H, W = map(int, input().split())
    c = [list(map(int, input().split())) for i in range(10)]
    A = [list(map(int, input().split())) for i in range(H)]
    #c = csgraph.floyd_warshall(c, False)
    for k in range(10):
        for i in range(10):
            for j in range(10):
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])
    #print(c)
    ans = 0
    for i in A:
        for j in i:
            if j != -1 and j != 1:
                ans += c[j][1]
                #print(c[j][1], j)
    print(int(ans))
ABC079D()

Submission status: Accepted

Solution code:
def ABC079D():
    H, W = map(int, input().split())
    c = [list(map(int, input().split())) for i in range(10)]
    A = [list(map(int, input().split())) for i in range(H)]
    #c = csgraph.floyd_warshall(c, False)
    for k in range(10):
        for i in range(10):
            for j in range(10):
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])
    #print(c)
    ans = 0
    for i in A:
        for j in i:
            if j != -1 and j != 1:
                ans += c[j][1]
                #print(c[j][1], j)
    print(int(ans))
ABC079D()

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
C = []
A = []
for i in range(10) :
    C.append(list(map(int,input().split())))
for i in range(H) :
    A.append(list(map(int,input().split())))
for i in range(10) :
    for j in range(10) :
        for k in range(10) :
            C[j][k] = min(C[j][k], C[j][i]+C[i][k])
ans = 0
for row in A :
    for a in row :
        if a == -1 or a == 1 :
            continue
        else :
            ans += C[a][1]
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
C = []
A = []
for i in range(10) :
    C.append(list(map(int,input().split())))
for j in range(H) :
    A.append(list(map(int,input().split())))
for k in range(10) :
    for l in range(10) :
        for m in range(10) :
            C[l][m] = min(C[l][m],C[l][k]+C[k][m])
ans = 0
for row in A :
    for n in row :
        if n == -1 :
            continue
        else :
            ans += C[n][1]
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
stdin = sys.stdin

 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def dijkstra(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

h,w = li()
graph = [[] for _ in range(10)]

for i in range(10):
    d = list(li())
    for j,dj in enumerate(d):
        graph[i].append((dj,j))
        
a = [list(li()) for _ in range(h)]

dist = [0]*10
for i in range(10):
    dist[i] = dijkstra(graph,10,i)[1]

ans = 0
for row in range(h):
    for col in range(w):
        if a[row][col] != -1:
            ans += dist[a[row][col]]
            
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
c = [list(map(int, input().split())) for i in range(10)]
a = [list(map(int, input().split())) for i in range(h)]

for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j] = min(c[i][j], c[i][k] + c[k][j])

ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == -1:
            continue
        ans += c[a[i][j]][1]

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
grid = []
for i in range(10):
    array = list(map(int, input().strip().split(' ')))
    grid.append(array)
wall = []
for i in range(h):
    array = list(map(int, input().strip().split(' ')))
    wall.append(array)
def warshall_floyd(n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j])
warshall_floyd(10)
cost=[]
for arrays in grid:
  cost.append(arrays[1])
ans = 0
for arrays in wall:
  for nums in arrays:
    if nums == -1:
      pass
    else:
      ans += cost[nums]
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
h,w = map(int, input().split())

c = []
for _ in range(10):
    line = list(map(int, input().split()))
    c.append(line)

for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j] = min(c[i][j], c[i][k]+c[k][j])

ret = 0
for _ in range(h):
    for a in map(int, input().split()):
        if a>=0:
            ret += c[a][1]

print(ret)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
cc = [[int(x) for x in input().split()] for i in range(10)]

for k in range(10):
    for i in range(10):
        for j in range(10):
            cc[i][j] = min(cc[i][j], cc[i][k] + cc[k][j])

ans = 0
for i in range(h):
    aa = map(int, input().split())
    for a in aa:
        if a >= 0:
            ans += cc[a][1]

print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
list1=[]
for i in range(10):
    A=list(map(int,input().split()))
    list1.append(A)

for c in range(10):
    for a in range(10):
        for b in range(10):
            if list1[a][b]>list1[a][c]+list1[c][b]:
                list1[a][b]=list1[a][c]+list1[c][b]
                
list2=[0,0,0,0,0,0,0,0,0,0]       
list3=[]
for d in range(H):
    w=list(map(int,input().split()))
    list3.append(w)
    
for e in range(H):
    for f in range(W):
        if abs(list3[e][f])==1:
            pass
        else:
            list2[list3[e][f]]+=1
ans=0
for g in range(10):
    ans+=list2[g]*list1[g][1]
print(ans)

Submission status: Accepted

Solution code:
ai = lambda: list(map(int, input().split()))

h,w = ai()
d = [ai() for _ in range(10)]

from scipy.sparse import csgraph
d = csgraph.floyd_warshall(d)

ans = 0

for _ in range(h):
    for aa in ai():
        if aa != -1:
            ans += int(d[aa][1])
print(ans)

Submission status: Accepted

Solution code:
ai = lambda: list(map(int, input().split()))

h,w = ai()
d = [ai() for _ in range(10)]
a = [ai() for _  in range(h)]

from scipy.sparse import csgraph
d = csgraph.floyd_warshall(d)

ans = 0
from itertools import chain
for aa in chain.from_iterable(a):
    if aa != -1:
        ans += int(d[aa][1])
print(ans)

Submission status: Accepted

Solution code:
h, w = list(map(int, input().split()))
c = [list(map(int, input().split())) for _ in range(10)]
a = [list(map(int, input().split())) for _ in range(h)]

for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j] = min(c[i][j], c[i][k]+c[k][j])

ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == -1:
            continue
        else:
            ans += c[a[i][j]][1]
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(10)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

wall = [list(map(int, input().split())) for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if wall[i][j] >= 0:
            num = wall[i][j]
            ans += d[num][1]

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
c = [list(map(int, input().split())) for k in range(10)]
A = [list(map(int, input().split())) for k in range(H)]

for p in range(10):
    for q in range(10):
        for r in range(10):
            c[q][r] = min(c[q][r], c[q][p]+c[p][r])

ans = 0
for k in range(H):
    for l in range(W):
        if A[k][l] >= 0:
            ans += c[A[k][l]][1]
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())

A = [list(map(int, input().split())) for _ in range(10)]

for a in range(10):
    for b in range(10):
        for c in range(10):
            A[b][c]=min(A[b][c],A[b][a]+A[a][c])

ans=0
D=[]
for j in range(H):
    C=list(map(int,input().split()))
    D.append(C)
        
for k in range(H):
    for l in range(W):
        if D[k][l]!=(-1) and D[k][l]!=(1):
            ans+=A[D[k][l]][1]
print(ans)

Submission status: Accepted

Solution code:
# ワーシャルフロイド法
H, W=list(map(int, input().split()))
c=[list(map(int, input().split())) for _ in range(10)]
A=[list(map(int, input().split())) for _ in range(H)]

for k in range(10):
    for i in range(10):
        for j in range(10):
            if c[i][j]>c[i][k]+c[k][j]:
                c[i][j]=c[i][k]+c[k][j]

ans=0
for h in range(H):
    for w in range(W):
        if A[h][w]!=-1 and A[h][w]!=-1:
            ans+=c[A[h][w]][1]
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
C = [[int(x) for x in input().split()] for _ in range(10)]
A = [[int(x) for x in input().split()] for _ in range(H)]

import heapq
def dijkstra(adj, n, st=1):
    inf = float('inf')
    dj = [inf] * (n + 1)
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                heapq.heappush(q, (dj[tn], tn))
    return dj

adj = dict((x, []) for x in range(10))
for i in range(10):
    for j in range(10):
        adj[j].append((i, C[i][j]))
costs = dijkstra(adj, 9, 1)

from itertools import chain
print(sum(costs[x] for x in chain(*A) if x != -1))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
C = [[int(x) for x in input().split()] for _ in range(10)]
A = [[int(x) for x in input().split()] for _ in range(H)]

import heapq
def dijkstra(adj, n, st=1):
    inf = float('inf')
    dj = [inf] * (n + 1)
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                heapq.heappush(q, (dj[tn], tn))
    return dj

adj = dict((x, []) for x in range(10))
for i in range(10):
    for j in range(10):
        adj[j].append((i, C[i][j]))
costs = dijkstra(adj, 9, 1)

ans = 0
for i in range(H):
    for j in range(W):
        a = A[i][j]
        if a == -1: continue
        ans += costs[a]
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
A = [list(map(int, input().split())) for _ in range(H)]

for k in range(10):
    for i in range(10):
        for j in range(10):
            if c[i][j] > c[i][k] + c[k][j]:
                c[i][j] = c[i][k] + c[k][j]

ans = 0
for h in range(H):
    for w in range(W):
        if A[h][w] != -1 and A[h][w] != 1:
            ans += c[A[h][w]][1]
print(ans)