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 warshall_floyd(d,n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

H,W = [int(x) for x in 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)]
cnt = 0
warshall_floyd(C,10)
for line in A:
    for a in line:
        if(a==-1):
            pass
        else:
            cnt += C[a][1]
print(cnt)

Submission status: Accepted

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


graph = list(zip(*graph))

vst = 1
n = 10
checked = [0] * n
dist = [float('inf')] * n
dist[vst] = 0
for _ in range(n):
    min_dist = float('inf')
    for i in range(n):
        if checked[i] == 0 and dist[i] < min_dist:
            target_v = i
            min_dist = dist[i]
    checked[target_v] = 1
    for to_v in range(n):
        cost = graph[target_v][to_v]
        dist[to_v] = min(dist[target_v] + cost, dist[to_v])



ret = 0
for i in range(h):
    for j in map(int, input().split()):
        if j != -1:
            ret += dist[j]


print(ret)

Submission status: Accepted

Solution code:
import numpy as np


h, w = map(int, input().split())
graph = [[] for _ in range(10)]
for i in range(10):
    graph[i] += list(map(int, input().split()))


graph = np.transpose(np.array(graph))

vst = 1
n = 10
checked = [0] * n
dist = [float('inf')] * n
dist[vst] = 0
for _ in range(n):
    min_dist = float('inf')
    for i in range(n):
        if checked[i] == 0 and dist[i] < min_dist:
            target_v = i
            min_dist = dist[i]
    checked[target_v] = 1
    for to_v in range(n):
        cost = graph[target_v][to_v]
        dist[to_v] = min(dist[target_v] + cost, dist[to_v])



ret = 0
for i in range(h):
    for j in map(int, input().split()):
        if j != -1:
            ret += dist[j]


print(ret)

Submission status: Accepted

Solution code:
import numpy as np


def dijkstra(cost_matrix, start_node=0):
    node_num = len(cost_matrix)
    distance = np.full(node_num, np.inf)
    distance[start_node] = 0
    unsearched_nodes = [i for i in range(node_num)]
    while unsearched_nodes:
        min_distance = np.inf
        for each_node in unsearched_nodes:
            if distance[each_node] < min_distance:
                min_distance = distance[each_node]
                target_node = each_node
        unsearched_nodes.remove(target_node)
        each_distance = cost_matrix[target_node]
        for i in range(node_num):
            if each_distance[i] != 0:
                distance[i] = min(distance[i], distance[target_node] + each_distance[i])
    return distance.astype(int)


h, w = map(int, input().split())
graph = np.array([np.array(list(map(int, input().split()))) for _ in range(10)])
graph = np.transpose(graph)
dist = dijkstra(graph, start_node=1)


wall_num = []
for i in range(h):
    wall_num += list(map(int, input().split()))



ret = 0
for num in wall_num:
    if num != -1:
        ret += dist[num]


print(ret)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import numpy as np



def dijkstra(graph, n, vst=0):
    distance = [float('inf')] * n
    distance[vst] = 0
    checked_v = [0] * n
    route = [''] * 10
    route[vst] = str(vst)
    dist = [float('inf')] * n
    dist[vst] = 0
    q = []
    heappush(q, (0, vst))
    for _ in range(n):
        while True:
            min_dist, search_v = heappop(q)
            if checked_v[search_v] == 0:
                break
        checked_v[search_v] = 1
        for to_v in range(n):
            if checked_v[to_v] == 0:
                cost = graph[search_v][to_v]
                if dist[search_v] + cost < dist[to_v]:
                    dist[to_v] = dist[search_v] + cost
                    route[to_v] = route[search_v] + str(to_v)
                    heappush(q, (dist[to_v], to_v))
    return dist


h, w = map(int, input().split())
graph = np.array([np.array(list(map(int, input().split()))) for _ in range(10)])
graph = np.transpose(graph)
dist = dijkstra(graph, 10, vst=1)


wall_num = []
for i in range(h):
    wall_num += list(map(int, input().split()))



ret = 0
for num in wall_num:
    if num != -1:
        ret += dist[num]


print(ret)

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):
        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())
cost = []
for _ in range(10):
    cost.append(list(map(int, input().split())))
wall = []
for _ in range(H):
    wall.append(list(map(int, input().split())))

dp = [[0 for _ in range(10)] for _ in range(10)]
for i in range(10):
    for j in range(10):
        dp[i][j] = cost[i][j]
for k in range(10):
    for i in range(10):
        for j in range(10):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

ans = 0
for h in range(H):
    for w in range(W):
        A = wall[h][w]
        if A >= 0:
            ans += dp[A][1]

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
  h, w = map(int, input().split())
  costs = []
  for _ in range(10):
    costs.append(list(map(int, input().split())))

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

  ans = 0
  for _ in range(h):
    alist = map(int, input().split())
    for a in alist:
      if a == -1:
        continue
      ans += costs[a][1]
  print(ans)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
d = []
for i in range(10):
    d.append(list(map(int, input().split())))
a = []
for i in range(h):
    a.append(list(map(int, input().split())))
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])

#for k in range(0, 10):
#    print(c[k])
#for k in range(0, 10):
#    print(d[k])
#print(d[8][1])

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
C = []
for _ in range(10):
    c = [int(s) for s in input().split()]
    C.append(c)
A = []
for _ in range(H):
    a = [int(s) for s in input().split()]
    for ai in a:
        if ai != -1:
            A.append(ai)
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 = sum([C[ai][1] for ai in A])
print(ans)

Submission status: Accepted

Solution code:
inf = float("inf")

H, W = map(int, input().split())
C = []
for _ in range(10):
    c = [int(s) for s in input().split()]
    C.append(c)
A = []
for _ in range(H):
    a = [int(s) for s in input().split()]
    for ai in a:
        if ai != -1:
            A.append(ai)
for _ in range(9):
    for i in range(10):
        for j in range(10):
            for k in range(10):
                C[i][j] = min(C[i][j], C[i][k] + C[k][j])
ans = sum([C[ai][1] for ai in A])
print(ans)

Submission status: Accepted

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


def warshall_floyd(d):
    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])
    return d


d = warshall_floyd(c)
cnt = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == -1:
            continue
        else:
            cnt += c[A[i][j]][1]
print(cnt)

Submission status: Accepted

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

def WarshallFloyd(lst):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                lst[i][j] = min(lst[i][j], lst[i][k] + lst[k][j])
#i --> 0　への最短経路問題
c = [list(map(int, input().split())) for _ in range(10)]
WarshallFloyd(c)

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

ans = 0
for i in A:
    for j in i:
        if j == -1:
            pass
        else:
            ans += c[j][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)]

INF = 10000

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 h in range(H):
    for w in range(W):
        a = A[h][w]
        if a == -1:
            continue
        ans += C[a][1]
print(ans)

Submission status: Accepted

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

cost = [float('inf')]*10
cost[1] = 0
for i in range(10):
    for y in range(10):
        for x in range(10):
            cost[x] = min(cost[x],cost[y]+c[x][y])

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

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
shortest = [[0 for i in range(10)] for j in range(10)]
path = []
for i in range(10):
    c = list(map(int,input().split()))
    for j in range(10):
        shortest[i][j] = c[j]
for i in range(10):
    for j in range(10):
        for k in range(10):
            shortest[j][k] = min(shortest[j][k],shortest[j][i]+shortest[i][k])

# print(shortest)

ans = 0
for i in range(h):
    q = list(map(int,input().split()))
    for j in range(w):
        if q[j] != -1:
            ans += shortest[q[j]][1]

print(ans)

Submission status: Accepted

Solution code:
H, M = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
A = [list(map(int, input().split())) for _ in range(H)]
ans = 0
def warshall_floyd(n):
    for i in range(n): #経由する点
        for j in range(n): #始点
            for k in range(n):  #終点
                c[j][k] = min(c[j][k], c[j][i] + c[i][k])

warshall_floyd(10)

for a in A:
    for ai in a:
        if ai == -1: pass
        else:
            ans += c[ai][1]
        
print(ans)

Submission status: Accepted

Solution code:
def solve(h, w, c, a):
    n = 10
    dp = c.copy()
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    ans = 0
    for i in range(h):
        for j in range(w):
            x = a[i][j]
            if x == -1:
                continue
            ans += dp[x][1]
    return ans

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)]
print(solve(h, w, c, a))

Submission status: Accepted

Solution code:

h, w = [ int(v) for v in input().split() ]
cost_list = [ [ int(v) for v in input().split() ] for i in range(10) ]


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

ans = 0

for i in range(h):
    line = [ int(v) for v in input().split() ]
    for j in line:
        if j not in [1,-1]:
            ans += cost_list[j][1]

print(ans)

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# W行H列, x[W][H]
def create_grid(W, H, value = 0):
    return [[ value for _ in range(H)] for _ in range(W)]

########
def warshall_floyd(G):
    # G[i][j]: iからjへの最短距離
    N = len(G)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    return G

if __name__ == "__main__":
    # https://atcoder.jp/contests/abc016/tasks/abc016_3
    H, W = l_inpl()

    # 隣接行列 G, 存在しない辺はINF
    G = []
    for i in range(10):
        l = l_inpl()
        G.append(l)

    
    G = warshall_floyd(G)
    l = []
    for _ in range(H):
        li = l_inpl()
        l.extend(li)
    ans = 0

    for i in range(0, 10):
        if i == 1:
            continue
        ans += G[i][1] * l.count(i)
    print(ans)

Submission status: Accepted

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

def Warshall_Floyd(d,N=None):
    if N==None : N = len(d)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])

Warshall_Floyd(C,10)
ans = sum(C[b][1] for a in A for b in a if b!= -1)

print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
C = [list(map(int,input().split())) for _ in [0]*10]
A = [list(map(int,input().split())) for _ in [0]*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 = sum(C[b][1] for a in A for b in a if b!= -1)

print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd(cost):
    # cost[i][j] : iからjへの最短距離
    for k in range(10):
        for i in range(10):
            for j in range(10):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    return cost


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

cost = warshall_floyd(cost)

ans = 0
for r in range(h):
    for c in range(w):
        frm = a[r][c]
        if frm == -1:
            continue
        ans += cost[frm][1]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC79 D

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

#全点対最短路問題(ワーシャルフロイド法)
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])
m = [list(map(int,input().split())) for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if m[i][j] == -1:
            continue
        if m[i][j] == 1:
            continue
        else:
            ans += d[m[i][j]][1]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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])

count = Counter()
for i in range(H):
    count.update(list(map(int, input().split())))
print(sum([c[i][1] * count[i] for i in range(10)]))

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
N=10
c=[[int(i) for i in input().split()] for i in range(N)]
A=[[int(i) for i in input().split()] for i in range(H)]
for i in range(N):
    for j in range(N):
        for k in range(N):
            if c[i][k]+c[k][j]<c[i][j]:
                c[i][j]=c[i][k]+c[k][j]
for i in range(N):
    for j in range(N):
        for k in range(N):
            if c[i][k]+c[k][j]<c[i][j]:
                c[i][j]=c[i][k]+c[k][j]
for i in range(N):
    for j in range(N):
        for k in range(N):
            if c[i][k]+c[k][j]<c[i][j]:
                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:
from sys import stdin
from numpy import array
from collections import defaultdict
from heapq import heappush, heappop


def solve(row):
    readline = stdin.readline
    g = defaultdict(list)

    for i in range(10):
        c_i = list(map(int, readline().split()))
        for j in range(10):
            g[i].append((c_i[j], j))

    accm = [0]*10
    for r in range(row):
        a = list(map(int, readline().split()))
        a = array(a)
        for ai in a:
            if ai != -1:
                accm[ai] += 1

    to_1 = []
    for k in range(10):
        from_k = dijkstra(10, g, k)
        to_1.append(from_k[1])

    return sum([to_1[i] * accm[i] for i in range(10)])


def dijkstra(vertex, g, sp):
    d = [float('inf')] * vertex
    d[sp] = 0
    heap = [(d[sp], sp)]

    while heap:
        du, u = heappop(heap)
        for length, v in g[u]:

            if d[v] > du + length:
                d[v] = du + length
                heappush(heap, (d[v], v))
    return d


if __name__ == '__main__':
    row, _ = map(int, input().split())
    print(solve(row))

Submission status: Accepted

Solution code:
inf=10**17

def tp(a,b):
    return min(a,b,inf)
def tt(a,b):
    return min(a+b,inf)
def tpdot(A,B):#N正方行列のみにかけ算を許す
    N=len(A)
    C=[[inf]*N for i in range(N)]
    for i in range(N):
        for j in range(N):
            num=inf
            for k in range(N):
                t=tt(A[i][k],B[k][j])
                num=tp(num,t)
            C[i][j]=num
    return C
def tpeye(N):
    C=[[inf]*N for i in range(N)]
    for i in range(N):
        C[i][i]=0
    return C
def tppower(A,k):
    N=len(A)
    S,T=tpeye(N),A
    x=k
    while x>0:
        if x%2==1:
            S=tpdot(S,T)
        x=x//2
        T=tpdot(T,T)
    return S

H,W=map(int,input().split())
A=[[0]*10 for i in range(10)]
for j in range(10):
    C=[int(i) for i in input().split()]
    for k in range(10):
        A[j][k]=C[k]
#print(A)
A=tppower(A,10)
ans=0
for j in range(H):
    C=[int(i) for i in input().split()]
    for k in range(W):
        if C[k]!=-1:
            ans+=A[C[k]][1]
#print(A)
print(ans)

Submission status: Accepted

Solution code:
def smaller(x, y):
	if x < y:
		return x
	return y

H, W = map(int, input().split())
C = []
for i in range(0, 10):
	C.append(list(map(int, input().split())))
A = []
for i in range(0, H):
	A.append(list(map(int, input().split())))
magic = []
for i in range(0, 10):
	magic.append(C[i][1])
for i in range(0, 10):
	notvisited = []
	for j in range(0, 10):
		notvisited.append(True)
	notvisited[i] = False
	queue = [[i, notvisited, 0]]
	while queue != []:
		now = queue.pop(0)
		if now[2] < magic[i]:
			if now[0] == 1:
				magic[i] = now[2]
			else:
				for j in range(0, 10):
					if now[1][j] and now[2]+C[now[0]][j] < magic[i]:
						newnotvisit = []
						for k in range(0, 10):
							if j == k:
								newnotvisit.append(False)
							else:
								newnotvisit.append(now[1][k])
						queue.append([j, newnotvisit, now[2]+C[now[0]][j]])
sum = 0
for i in range(0, H):
	for j in range(0, W):
		if A[i][j] != -1:
			sum += magic[A[i][j]]
print(sum)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
c=[list(map(int,input().split())) for _ in [0]*10]
a=[list(map(int,input().split())) for _ in [0]*H]
def dp(i,j,l,lim):
    if lim<0:
        return 10**4
    else:
        return min([c[i][j]]+[c[i][k]+dp(k,j,l+[k],lim-c[i][k]) for k in range(10) if k not in l])
cc=[dp(i,1,[i,1],c[i][1]) for i in range(10)]
print(sum([cc[j] for i in a for j in i if j!=-1]))