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 8 s, 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

Solution (Python):
H,W=map(int,input().split())
lc=[]
for i in range(10):
    lc.append(list(map(int,input().split())))
la=[]
for i in range(H):
    la.append(list(map(int,input().split())))
for k in range(10):
    for i in range(10):
        for j in range(10):
            lc[i][j]=min(lc[i][j],lc[i][k]+lc[k][j])
ans=0
for i in range(H):
    for j in range(W):
        if la[i][j]!=-1:
            ans+=lc[la[i][j]][1]
print(ans)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W = MI()
    N=10
    def warshall_floyd(d, N):
        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])

    d=[[float("inf")] * N for i in range(N)]
    for i in range(N):
        d[i][i] = 0
    
    
    for i in range(N):
        C = LI()
        for j in range(N):
            d[i][j] = min(d[i][j], C[j])
    warshall_floyd(d, N)

    to = 1
    ans = 0
    for i in range(H):
        wall = LI()
        for j in range(W):
            num = wall[j]
            if num==-1:
                continue
            
            ans += d[num][to]
    
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

def main():
    H, W = map(int, sys.stdin.readline().split())
    ca = np.array(sys.stdin.read().split(), dtype=np.int64)
    cost = ca[:100].reshape(10, 10)
    A = ca[100:]
    
    min_cost = floyd_warshall(csgraph=csr_matrix(cost), directed=True)

    total_cost = min_cost[np.absolute(A)].T[1].astype(np.int64).sum()
    print(total_cost)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

def main():
    H, W = map(int, sys.stdin.readline().split())
    cost = np.array([sys.stdin.readline().split() for _ in range(10)], dtype=np.int64)
    A = np.array(sys.stdin.read().split(), dtype=np.int64)
    
    graph = csr_matrix(cost)
    dist = floyd_warshall(csgraph=graph, directed=True)

    ans = dist[np.absolute(A)].T[1].astype(np.int64).sum()
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    h, w = map(int, input().split())
    cc = [list(map(int, input().split())) for _ in range(10)]
    
    cnt = [0] * 10
    for _ in range(h):
        for a in map(int, input().split()):
            if a == -1: continue
            cnt[a] += 1
    

    
    cto1 = [-1] * 10
    hp = []
    heappush(hp, [0, 1])
    while hp:
        cost, u = heappop(hp)
        if cto1[u] != -1: continue
        cto1[u] = cost
        for v in range(10):
            if cto1[v] != -1: continue
            heappush(hp, [cost + cc[v][u], v])
    

    
    ans = sum(an * ac for an, ac in zip(cnt, cto1))
    print(ans)

main()

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy


from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])

def graphm():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(m):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((w,b))
        g[b].append((w,a))
    return n,m,g

def warshall_floyd(): 
    h,w = map(int,input().split()) 
    d = []
    for _ in range(10):
        d.append(inpl())
    n=10
    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])
    a=[]
    for _ in range(h):
        a.append(inpl())
    pre = []
    for i in range(10):
        pre.append(d[i][1])
    check = defaultdict(int)
    for i in range(h):
        for j in range(w):
            if a[i][j]==-1:
                continue
            check[a[i][j]]+=1
    ans=0
    for i in range(10):
        ans += pre[i]*check[i]
    print(ans)

def main(): 
    warshall_floyd()

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    h,w=map(int,input().split())
    C=[list(map(int,input().split())) for _ in range(10)]

    
    from itertools import product
    for k,i,j in product(range(10),repeat=3):
        C[i][j]=min(C[i][j],C[i][k]+C[k][j])

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

    ans=0
    for i,j in product(range(h),range(w)):
        a=A[i][j]
        if(a==-1): continue
        ans+=C[a][1]
    print(ans)
resolve()

Solution (Python):
from sys import stdin

inf = 10**10

h,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(10)]

lin = [list(map(int,stdin.readline().rstrip().split())) for _ in range(h)]

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

li = warshall_floyd(li)
liv = []
for i in range(10):
    liv.append(li[i][1])

point = 0
for i in range(h):
    for j in range(w):
        if lin[i][j] == -1:
            continue
        point += liv[lin[i][j]]

print(point)

Solution (Python):
H,W = [int(i) for i in input().split()]
ccc = []
AAA = []
for i in range(10):
    ccc.append([int(i) for i in input().split()])
for i in range(H):
    AAA.append([int(i) for i in input().split()])

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

ans = 0
for h in range(H):
    for w in range(W):
        if AAA[h][w] != -1:
            ans += ccc[AAA[h][w]][1]

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)

INF = 1000000


def main():
    H, W = map(int, input().split())
    adj_matrix = [[int(c) for c in input().split()] for i in range(10)]
    
    A = [[int(c) for c in input().split()] for i in range(H)]

    def solve(now, S, dp):
        if now == 1:
            dp[now][S] = 0
            return dp[now][S]
        elif dp[now][S] != INF:
            
            return dp[now][S]
        else:
            res = INF
            for i in range(10):
                if i == now:
                    continue
                if not (S >> i & 1):
                    res = min(res, solve(i, S | (1 << i), dp) + adj_matrix[now][i])
            dp[now][S] = res
            return dp[now][S]

    minimum_distance = {}
    for i in range(10):
        dp = [[INF for c in range(1 << 10)] for i in range(10)]
        minimum_distance[i] = solve(i, 1 << i, dp)

    wall_num = {i: 0 for i in range(10)}
    for line_ in A:
        for value_ in line_:
            if value_ == -1:
                continue
            else:
                wall_num[value_] += 1
    ans = 0
    for i in range(10):
        ans += wall_num[i] * minimum_distance[i]
    print(ans)

    

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    H, W = map(int, input().split())
    cost = 0
    digit = []
    for i in range(10):
        digit.append([])
        a = [int(i) for i in input().split()]
        digit[i] = a

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

    for i in range(H):
        A = [int(i) for i in input().split()]
        for j in range(W):
            if A[j] >= 0:
                cost += digit[A[j]][1]
    print(cost)
    




if __name__ == "__main__":
    main()

Solution (Python):
def dijkstra_heap(n,s,edge):
    
    d = [float("inf")] * n
    used = [True] * n  
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heappush(edgelist, e)
    while len(edgelist):
        minedge = heappop(edgelist)
        
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heappush(edgelist, [e[0] + d[v], e[1]])
    return d
def examD():
    H, W = LI()
    c = [LI() for _ in range(10)]
    A = [LI() for _ in range(H)]
    edge = [[] for i in range(10)]
    
    for i in range(10):
        for j in range(10):
            x, y, z = i, j, c[i][j]
            edge[x].append([z, y])
    res = []
    for i in range(10):
        res.append(dijkstra_heap(10, i, edge))

    d = defaultdict(int)
    for l in A:
        for j in l:
            d[j] +=1
    ans = 0
    for i in range(10):
        ans += d[i]*res[i][1]
    print(ans)

import sys,copy,bisect,itertools
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, atan2
from operator import mul
from functools import reduce
sys.setrecursionlimit(10 ** 9)

INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7



def dijkstra(G, s=0):
    n = len(G)
    que = [(0, s)]
    dist = [INF] * n
    dist[s] = 0
    while que:
        min_dist, u = heappop(que)
        if min_dist > dist[u]:
            continue
        for v, c in enumerate(G[u]):
            if dist[u] + c < dist[v]:
                dist[v] = dist[u] + c
                heappush(que, (dist[u] + c, v))
    return dist


h, w = LI()
G = LIR(10)
G = [i for i in zip(*G)]
dist = dijkstra(G, 1)
A = LIR(h)
ret = 0
for y in range(h):
    for x in range(w):
        if A[y][x] != -1:
            ret += dist[A[y][x]]


print(ret)

Solution (Python):
H,W=map(int,input().split())
lc=[]
for i in range(10):
    lc.append(list(map(int,input().split())))
la=[]
for i in range(H):
    la.append(list(map(int,input().split())))
for k in range(10):
    for i in range(10):
        for j in range(10):
            lc[i][j]=min(lc[i][j],lc[i][k]+lc[k][j])
ans=0
for i in range(H):
    for j in range(W):
        if la[i][j]!=-1:
            ans+=lc[la[i][j]][1]
print(ans)

Solution (Python):
H, W = map(int, input().split())
C = []
V = 10
ctr = [0 for _ in range(V)]

for _ in range(V):
	C.append(list(map(int, input().split())))
	
for _ in range(H):
	A = list(map(int, input().split()))
	for i in range(W):
		if A[i] != -1:
			ctr[A[i]] += 1
			
for k in range(V):
	for i in range(V):
		for j in range(V):
			if C[i][j] > C[i][k] + C[k][j]:
				C[i][j] = C[i][k] + C[k][j]
				
ans = 0
for i in range(V):
	ans += ctr[i] * C[i][1]
	
print(ans)

Solution (Python):
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):
            x = C[i][k] + C[k][j]
            if x < C[i][j]:
                C[i][j] = x

answer = 0
for x in A:
    for y in x:
        if y >= 0:
            answer += C[y][1]
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
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)]
res = 0
for k in range(10):
  for i in range(10):
    for j in range(10):
      c[i][j] = min(c[i][k] + c[k][j], c[i][j])
for y in range(H):
  for x in range(W):
    if (a[y][x] != -1) or (a[y][x] == 1):
      res += c[a[y][x]][1]
print(res)

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
ans = 0
H, W = map(int, input().split())
c = []
for i in range(10):
    tc = list(map(int, input().split()))
    c.append(tc)
c = np.array(c)
short = shortest_path(c)

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

Solution (Python):
H,W = [int(i) for i in input().split(' ')]
C = [[int(i) for i in input().split(' ')]for _ in range(10)]
 
prev = [-1]*10
row = [int(i) for i in range(10)]
ansewrDict = {}
total = 0

for v in row:
    ansewr = {str(i): 1000 for i in range(10)}
    d = {str(i) : 1000 for i in range(10)}
    if v == -1:
        continue
    s = v
    d[str(s)] = 0
    
    while d:
        u = min(d, key=d.get)
        ansewr[u] = d.pop(u)

        for i in range(10):
            if ansewr[str(i)] > ansewr[u] + C[int(u)][i]:
                d[str(i)] = ansewr[u] + C[int(u)][i]
                ansewr[str(i)] = ansewr[u] + C[int(u)][i]
    
    ansewrDict[str(v)] = ansewr

for _ in range(H):
    row = input().split(' ')
    for v in row:
        if v == '1' or v == '-1':
            continue
        
        total += ansewrDict[v]['1']
print(total)

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

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 i in range(H):
    for j in range(W):
        if A[i][j] != -1:
            ans += C[A[i][j]][1]
            
print(ans)

Solution (Python):


import collections

H,W=map(int,input().split())

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

cost=[[0]*10 for _ in range(10)]

dp=[table[i][1] for i in range(10)]


for n in range(10):
    temp=dp[:]
    for i in range(10):
        for j in range(10):
            temp[i]=min(table[i][j]+dp[j] if j!=i else temp[i],temp[i])
    dp=temp[:]


c=collections.Counter("")
for _ in range(H):
    c+=collections.Counter(list(map(int,input().split())))


ans=0
for item in c.items():
    if item[0]==-1:
        continue
    else:
        ans+=dp[item[0]]*item[1]

print(ans)

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

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
mod = 10**9 + 7
inf = float('inf')
ans = int(0)
H, W = LI()
c = [LI() for _ in range(10)]
A = [LI() for _ in range(H)]
d = [[float("inf") for i in range(10)] for i in range(10)]

for i in range(10):
    for j in range(10):
        d[i][j] = c[i][j]
for i in range(10):
    d[i][i] = 0 

L = warshall_floyd(10,d)
cur = int(0)
for i in range(H):
    for j in range(W):
        l = A[i][j]
        if l>=0:
            cur += L[l][1]

ans = cur
print(ans)

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

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
mod = 10**9 + 7
inf = float('inf')
ans = int(0)
H, W = LI()
c = [LI() for _ in range(10)]
A = [LI() for _ in range(H)]
d = [[float("inf") for i in range(10)] for i in range(10)]

for i in range(10):
    for j in range(10):
        d[i][j] = c[i][j]
for i in range(10):
    d[i][i] = 0 

L = warshall_floyd(10,d)
cur = int(0)
for i in range(H):
    for j in range(W):
        l = A[i][j]
        if l>=0:
            cur += L[l][1]

ans = cur
print(ans)

Solution (Python):
H,W = map(int,input().split())
Data = []
for i in range(10):
    Data.append(list(map(int,input().split())))
Wall = []
for _ in range(H):
    Wall.append(list(map(int,input().split())))

for k in range(10):
    for i in range(10):
        for j in range(10):
            Data[i][j] = min(Data[i][j],Data[i][k]+Data[k][j])
ans = 0
for h in range(H):
    for w in range(W):
        num = Wall[h][w]
        if num != -1:
            ans += Data[num][1]
print(ans)

Solution (Python):

import sys

H,W=map(int, sys.stdin.readline().split())
dp=[ [ float("inf") for j in range(10) ] for i in range(10) ]

for i in range(10):
    c=map(int, sys.stdin.readline().split())
    for j,x in enumerate(c):
        dp[i][j]=x



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 _ in range(H):
    A=map(int, sys.stdin.readline().split())
    for a in A:
        if a==-1: continue
        ans+=dp[a][1]

print ans

Solution (Python):

def warshall_floyd(n, d):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i] + d[i][k])


H, W = map(int, input().split())

N = 10
d = [None] * N
for i in range(N):
    d[i] = list(map(int, input().split()))
warshall_floyd(N, d)

result = 0
for _ in range(H):
    for i in map(int, input().split()):
        if i == -1:
            continue
        result += d[i][1]
print(result)

Solution (Python):

def warshall_floyd(n, d):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i] + d[i][k])


H, W = map(int, input().split())

N = 10
d = [None] * N
for i in range(N):
    d[i] = list(map(int, input().split()))
warshall_floyd(N, d)

m = [d[i][1] for i in range(N)]

result = 0
for _ in range(H):
    for i in map(int, input().split()):
        if i == -1:
            continue
        result += m[i]
print(result)

Solution (Python):

def warshall_floyd(n, d):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i] + d[i][k])


H, W = map(int, input().split())

N = 10
d = [None] * N
for i in range(N):
    d[i] = list(map(int, input().split()))
warshall_floyd(N, d)

m = [d[i][1] for i in range(N)]

result = 0
for i in range(H):
    for j in map(int, input().split()):
        if j == -1:
            continue
        result += m[j]
print(result)

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

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 Ai in A:
    if Ai != -1:
        ans += c[Ai][1]
print(ans)

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

H, W = map(int, input().split())
C = np.array([list(map(int, input().split())) for _ in range(10)])
A = [list(map(int, input().split())) for _ in range(H)]

C_new = np.where(C == 0, 10**9, C)
G = csgraph_from_dense(C_new, null_value=10**9)
d = floyd_warshall(G)

ans = 0
for line in A:
  for i in line:
    if i != -1:
      ans += d[i, 1]
      
print(int(ans))

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

A=[]
for i in range(H):
    A+=list(map(int,input().split()))
A.sort()
while A[0]==-1:
    A.pop(0)

def warshall_floyd(D,n):  
    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

True_Map = warshall_floyd(C,10)

ans=0
for i in A:
    ans+=True_Map[i][1]
print(ans)

Solution (Python):
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)]
lst=[0]*10
for i in range(h):
    for j in range(w):
        A=a[i][j]
        if A!=-1:
            lst[A]+=1
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])
lst[1]=0
ans=0
for i in range(10):
    ans+=c[i][1]*lst[i]
print(ans)

Solution (Python):
h, w = map(int, input().split())
dist = [list(map(int, input().split())) for _ in range(10)]
n = len(dist)
for k in range(n):
  for i in range(n):
    for j in range(n):
      if dist[i][j] > dist[i][k] + dist[k][j]:
        dist[i][j] = dist[i][k] + dist[k][j]       
list_a = [list(map(int, input().split())) for _ in range(h)]
result = 0
for one_row in list_a:
  for one_a in one_row:
    if one_a != -1:
      result += dist[one_a][1]
print(result)

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


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

n=10
warshall_floyd(c)


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)

Solution (Python):

import numpy as np
from scipy.sparse.csgraph import shortest_path

H, W = list(map(int, input().split()))

c_table = []

for _ in range(10):
    c_table.append(list(map(int, input().split())))

a_table = []

for _ in range(H):
    a_table.append(list(map(int, input().split())))

c_table = np.array(c_table)
a_table = np.array(a_table)

d_matrix = shortest_path(c_table)
cost = 0

for h in range(H):
    a_list = a_table[h]
    for a in a_list:
        if a == -1:
            continue
        cost += d_matrix[a][1]

ans = int(cost)
print(ans)

Solution (Python):
a,b = map(int,input().split())
cost = [[int(i) for i in input().split()] for j in range(10)]
ans = 0
for k in range(10):
    for i in range(10):
        for j in range(10):
            if cost[i][k] < 10000 and cost[k][j] < 10000:
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
for i in range(a):
  for j in input().split():
    j = int(j)
    if j == 0 or 2 <= j <= 9:
      ans += cost[j][1]
print(ans)

Solution (Python):
import copy
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)]
d=copy.deepcopy(C)
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])
ans=0
for al in A:
    for a in al:
        if a!=-1:
            ans+=d[a][1]
print(ans)

Solution (Python):
h,w=map(int,input().split())
c=[]
for i in range(10):
    c.append(list(map(int,input().split())))
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):
    s=list(map(int,input().split()))
    for j in s:
        if j!=1 and j!=-1:
            ans+=c[j][1]
print(ans)

Solution (Python):
n,m=map(int,input().split())
mat=[]
for i in range(10):
    mat.append([int(i) for i in input().split()])

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

ans=0
for i in range(n):
    l=[int(x) for x in input().split()]
    for z in l:
        if z!=-1 and z!=1:
           
            ans+=mat[z][1]
print(ans)

Solution (Python):
h,w = map(int,input().split())
cst = []

for i in range(10):
    cst.append(list(map(int,input().split())))

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

li = [10**4 for i in range(10)] 
li[1] = 0

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

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

print(ans)

Solution (Python):
H,W=map(int,input().split())
C=[1001]*10
C[1]=0

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

for _ in range(10):
  for i in range(10):
    if i!=1:
      for j in range(10):
        if i!=j:
          if C[i]>c[i][j]+C[j]:
            C[i]=c[i][j]+C[j]
          
ans=0        
for i in range(H):
  for j in list(map(int,input().split())):
    if j!=-1:
      ans+=C[j]
print(ans)

Solution (Python):
H,W=map(int,input().split())
INF=float('inf')
cost=[[INF]*10 for _ in range(10)]
for i in range(10):
  tmp=list(map(int,input().split()))
  for j in range(10):
    cost[i][j]=tmp[j]
def warshal_floyd(cost):
  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
ans=0
min_cost=warshal_floyd(cost)
for i in range(H):
  tmp=list(map(int,input().split()))
  for j in range(W):
    if tmp[j]==-1 or tmp[j]==1:
      pass
    else:
      ans+=min_cost[tmp[j]][1]                 
print(ans)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall


h, w = list(map(int, input().split()))

c = [0 for i in range(10)]
for i in range(10):
    c[i] = list(map(int, input().split()))

wall = []

for i in range(h):
    wall.append(list(map(int, input().split())))



costone = [(10**3) + 1 for i in range(11)]

costone[1] = 0

costone[10] = 0


c = floyd_warshall(c)





for i in range(10):
    costone[i] = min(costone[i], c[i][1])
sum = 0


for i in range(h):
    for j in range(w):
        sum += costone[wall[i][j]]
print(int(sum))

Solution (Python):
h, w = map(int, input().split())
n = 10
g = [None] * n
for i in range(n):
    g[i] = list(map(int, input().split()))

def warshall_floyd(d, n):
    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

cost = warshall_floyd(g, n)
ans = 0
for _ in range(h):
    for w in list(map(int, input().split())):
        if w == -1: continue
        ans += cost[w][1]
print(ans)

Solution (Python):
def warshall_floyd(n, d):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i] + d[i][k])


H, W = map(int, input().split())

N = 10
d = [None] * N
for i in range(N):
    d[i] = list(map(int, input().split()))

warshall_floyd(N, d)

c = {i: 0 for i in range(N)}
for i in range(H):
    for j in map(int, input().split()):
        if j == -1:
            continue
        c[j] += 1

print(sum(c[i] * d[i][1] for i in range(N)))