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):
from heapq import heappush, heappop


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

INF = float("inf")
graph1 = []

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

graph2 = [[] for _ in range(10)]
for i in range(10):
    for j in range(10):
        graph2[i].append((graph1[i][j], j))

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


def dijkstra(graph:list, node:int, start:int) -> list:
    
    INF = float("inf")
    dist = [INF]*node
    
    
    dist[start] = 0
    heap = [(0,start)]
    
    
    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

dist_to1 = []
for i in range(10):
    dist = dijkstra(graph2, 10, i)
    dist_to1.append(dist[1])

ans = 0
for h in range(H):
    for w in range(W):
        if A[h][w] == -1:
            continue
        else:
            ans += dist_to1[A[h][w]]
    
print(ans)

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

import heapq
def dijkstra(adj, n, st=1):
    dj = [2**64] * (n + 1)
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        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 = {}
for j in range(10):
    t = []
    for i in range(10):
        t.append([i, C[i][j]])
    adj[j] = t
costs = dijkstra(adj, 9, 1)

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

Solution (Python):
from collections import defaultdict
from scipy.sparse.csgraph import floyd_warshall
H, W = map(int, input().split())
C = []
for i in range(10):
    ci = [int(cij) for cij in input().split()]
    C.append(ci)

A = defaultdict(int)
for i in range(H):
    for Aij in input().split():
        A[int(Aij)] += 1
if -1 in A:
    del A[-1]

D = floyd_warshall(C)
cost = 0
for k, v in A.items():
    cost += D[k][1] * v
print(int(cost))

Solution (Python):
H, W = map(int, input().split())
C = [[int(x) for x in input().split()] for i in range(10)]
preC = [c[:] for c in C]
for l in range(10):
  postC = [c[:] for c in preC]
  for i in range(10):
    for j in range(10):
      for k in range(10):
        postC[i][j] = min(preC[i][k] + C[k][j], postC[i][j])
  preC = [c[:] for c in postC]
L = [postC[i][1] for i in range(10)]
A = [[int(x) for x in input().split()] for i in range(H)]
ans = 0
for Ai in A:
  for Aij in Ai:
    if Aij > -1:
      ans += L[Aij]
print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def warshall_floyd(g):
    d = defaultdict(dict)
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v))
    V = set(V)
    for i in V:
        for j in V:
            if i in g and j in g[i]:
                d[i][j] = g[i][j]
            else:
                d[i][j] = sys.maxsize
    for k in g:
        for i in g:
            for j in g:
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

    return d


@mt
def slv(H, W, C, A):
    g = defaultdict(dict)
    for i in range(10):
        for j in range(10):
            g[i][j] = C[i][j]

    d = warshall_floyd(g)

    a = Counter()
    for r in A:
        for n in r:
            a[n] += 1

    ans = 0
    for k in a:
        if k != -1:
            ans += d[k][1] * a[k]
    return ans


def main():
    H, W = read_int_n()
    C = [read_int_n() for _ in range(10)]
    A = [read_int_n() for _ in range(H)]
    print(slv(H, W, C, A))


if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush, heappop
INF = 10 ** 10
h, w = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(10)]

cost_to_one = []
for i in range(10):
  costs = [INF] * 10
  que = []
  heappush(que, (0, i))
  costs[i] = 0
  while que:
    dist, node = heappop(que)
    for to, v in enumerate(edges[node]):
      if costs[to] > dist + v:
        costs[to] = dist + v
        heappush(que, (dist + v, to))
  cost_to_one.append(costs[1])

cost_to_one.append(0)
ans = 0
for _ in range(h):
  lst = list(map(int, input().split()))
  for i in lst:
    ans += cost_to_one[i]

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 x 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 and a[i][j] != -1:
            ans += c[a[i][j]][1]

print(ans)

Solution (Python):

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

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

Solution (Python):
N, INF = 10, 1 << 40
M = [[INF for j in range(N)] for i in range(N)]
dist = [[INF for l in range(N)] for m in range(N)]


def dijkstra(s):
    check = [0 for i in range(N)]
    dist[s][s] = 0

    while True:
        min_cost, u = INF, -1
        for i in range(N):
            if check[i] != 2 and dist[s][i] < min_cost:
                min_cost = dist[s][i]
                u = i

        if min_cost == INF:
            break

        check[u] = 2

        for v in range(N):
            if check[v] != 2 and M[u][v] != INF:
                if dist[s][u] + M[u][v] < dist[s][v]:
                    dist[s][v] = dist[s][u] + M[u][v]
                    check[v] = 1


def main():
    h, w = map(int, input().split())
    for i in range(N):
        low = list(map(int, input().split()))
        for j in range(N):
            if low[j] != 0:
                M[i][j] = low[j]

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

    for i in range(N):
        dijkstra(i)

    cost = 0
    for i in range(h):
        for j in range(w):
            if grid[i][j] != -1:
                num = grid[i][j]
                cost += dist[num][1]

    print(cost)


if __name__ == '__main__':
    main()

Solution (Python):
b=input().split(" ")
a0=input().split(" ")
a1=input().split(" ")
a2=input().split(" ")
a3=input().split(" ")
a4=input().split(" ")
a5=input().split(" ")
a6=input().split(" ")
a7=input().split(" ")
a8=input().split(" ")
a9=input().split(" ")
array=[a0,a1,a2,a3,a4,a5,a6,a7,a8,a9]
cost=0
for k in range(10):
	for i in range(10):
		for j in range(10):
			array[i][j]=min(int(array[i][j]),int(array[i][k])+int(array[k][j]))
for i in range(int(b[0])):
	lines=input().split()
	for j in range(int(b[1])):
		if int(lines[j])!=-1:
			cost+=int(array[int(lines[j])][1])
print(cost)

Solution (Python):
from collections import defaultdict
from itertools import product

H, W = map(int, input().split())
c = [[int(x) for x in input().split()] for _ in range(10)]
A = defaultdict(int)
for _ in range(H):
    for x in input().split():
        x = int(x)
        if x != -1 and x != 1:
            A[x] += 1

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

ans = 0
for k, v in A.items():
    ans += c[k][1] * v
print(ans)

Solution (Python):
from collections import defaultdict
from itertools import product

H, W = map(int, input().split())
c = [[int(x) for x in input().split()] for _ in range(10)]
A = defaultdict(int)
for _ in range(H):
    for x in input().split():
        x = int(x)
        if x != -1 and x != 1:
            A[x] += 1

for _, i, j, k in product(range(10), range(10), range(10), range(10)):
    if i == 1 or k == 1:
        continue
    c[i][j] = min(c[i][j], c[i][k] + c[k][j])

ans = 0
for k, v in A.items():
    ans += c[k][1] * v
print(ans)

Solution (Python):
import math


def make_list(V,E):
 
    edges = []
    path=[[float("inf")]*E for i in range(V) ]   
    
    for i in range(V):
        a=[int(x) for x in str(input()).split()]
        for j in range(len(a)):
            
            path[i][j]=i
           
                
                
	
        edges.append((a))    
	

   
     
    return edges ,path



def warshall_floyd(glath,path):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
                                   path[i][j] = path[k][j]
				
				
	return glath,path





H, W = [int(x) for x in str(input()).split()]  

cost_graph,graph=make_list(10,10)
wall ,wall_graph= make_list(H,W)
    

un_label=[]
for i in wall:
   for j in i: 
            if j !=-1 and j!=1:
                 un_label.append(j)
cost=0
 
all_cost,all_graph=warshall_floyd(cost_graph,graph)
    
   

for i in un_label:
        cost+=all_cost[i][1]

print(cost)

Solution (Python):
import math


def make_list(V,E):
 
    edges = []
    path=[[0]*E for i in range(V) ]   
    
    for i in range(V):
        a=[int(x) for x in str(input()).split()]
        for j in range(len(a)):
            
            path[i][j]=i
           
                
                
	
        edges.append((a))    
	

   
     
    return edges ,path



def warshall_floyd(glath,path):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
                                   path[i][j] = path[k][j]
				
				
	return glath,path





H, W = [int(x) for x in str(input()).split()]  

cost_graph,graph=make_list(10,10)
wall ,wall_graph= make_list(H,W)
    

un_label=[]
for i in wall:
   for j in i: 
            if j !=-1 and j!=1:
                 un_label.append(j)
cost=0
 
all_cost,all_graph=warshall_floyd(cost_graph,graph)
    
   

for i in un_label:
        cost+=all_cost[i][1]

print(cost)

Solution (Python):
d=input().split(" ")
a0=input().split(" ")
a1=input().split(" ")
a2=input().split(" ")
a3=input().split(" ")
a4=input().split(" ")
a5=input().split(" ")
a6=input().split(" ")
a7=input().split(" ")
a8=input().split(" ")
a9=input().split(" ")
AA=[a0,a1,a2,a3,a4,a5,a6,a7,a8,a9]
stop=0
for k in range(10):
    for i in range(10):
        for j in range(10):
            AA[i][j]=min(int(AA[i][j]),int(AA[i][k])+int(AA[k][j]))
for i in range(int(d[0])):
    gear=input().split()
    for j in range(int(d[1])):
        if int(gear[j])!=-1:
            stop+=int(AA[int(gear[j])][1])
print(stop)

Solution (Python):



H,W=[int(x) for x in str(input()).split()]
c=[]
for i in range(0,10):
  c.append([int(x) for x in str(input()).split()])

A=[]
A.append([0 for i in range(0,W+1)])
for i in range(1,H+1):
  A.append([0]+[int(x) for x in str(input()).split()])

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


abc=[]
for i in range(0,10):
  abc.append(c[i][1])

count=0

for i in range(1,H+1):
  for j in range(1,W+1):
    if A[i][j]!=-1:
      count+=abc[A[i][j]]
print(count)

Solution (Python):
x=input().split()
h=int(x[0])
w=int(x[1])
c=[[]*10 for i in range(10)]
for i in range(10):
    y=input().split()
    x=0
    while x<10:
        y[x]=int(y[x])
        x=x+1
    c[i].extend(y)
    
a=[[]*w for i in range(h)]

for i in range(h):
    y=input().split()
    x=0
    while x<w:
        y[x]=int(y[x])
        x=x+1
    a[i].extend(y)
    
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])
cost=0
for i in range(h):
    for j in range(w):
        if a[i][j]!=-1:
            cost=cost+c[a[i][j]][1]
print(cost)

Solution (Python):
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])
print(sum(sum(C[i][1] for i in AA if i >= 0) for AA in A))

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):
			if c[i][k] + c[k][j] < c[i][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:
			ans += c[A[h][w]][1]

print(ans)

Solution (Python):
import numpy as np

H, W = map(int, input().split())
C = []
for i in range(10):
    C.append(list(map(int, input().split())))
CT = np.array(C).T
W = [0] * 10
for i in range(H):
    for j in map(int, input().split()):
        if j != -1:
            W[j] += 1

D = [0] * 10
Open = list(CT[1])
Open[1] = -1
for j in range(9):
    p = min([l for l in enumerate(Open) if l[1] != -1], key=lambda x: x[1])
    D[p[0]] = p[1]
    Open[p[0]] = -1
    for i in range(10):
        Open[i] = min(Open[i], CT[p[0]][i] + p[1])
ans = 0
for i in range(10):
    ans += D[i] * W[i]
print(ans)

Solution (Python):
from heapq import heappush,heappop
H,W = map(int,input().split())
inf=10**10

dp=[[[inf]*10 for i in range(10)]for i in range(11)]
for j in range(10):
    c=[int(k) for k in input().split()]
    for i in range(10):
        dp[0][i][j]=c[i]

A=[[int(i) for i in input().split()] for i in range(H)]
for k in range(1,11):
    for j in range(10):
        for i in range(10):
            dp[k][j][i]=min(dp[k-1][j][i],dp[k-1][j][k-1]+dp[k-1][k-1][i])
ans =0
for i in range(W):
    for j in range(H):
        if A[j][i]!=-1 and A[j][i]!=1:
            ans += dp[10][1][A[j][i]]
print(ans)

Solution (Python):
from heapq import heappush,heappop
H,W = map(int,input().split())
inf=10**10

dp=[[[inf]*10 for i in range(10)]for i in range(11)]
for j in range(10):
    c=[int(k) for k in input().split()]
    for i in range(10):
        dp[0][i][j]=c[i]

A=[[int(i) for i in input().split()] for i in range(H)]
for k in range(1,11):
    for j in range(10):
        for i in range(10):
            dp[k][j][i]=min(dp[k-1][j][i],dp[k-1][j][k-1]+dp[k-1][k-1][i])
ans =0
for i in range(W):
    for j in range(H):
        if A[j][i]!=-1 and A[j][i]!=1:
            ans += dp[10][1][A[j][i]]
print(ans)

Solution (Python):
from heapq import heappush,heappop
H,W = map(int,input().split())
table=[[] for i in range(10)]
for i in range(10):
    c=[int(k) for k in input().split()]
    for j in range(10):
        if i==j:
            continue
        table[j].append([i,c[j]])
A=[[int(i) for i in input().split()] for i in range(H)]


kei=[]
val=[10**9]*(10)
val[1]=0
heappush(kei,(0,1))
while kei:
    d,i = heappop(kei)
    if d > val[i]:
        continue
    for x,q in table[i]:
        if val[x]>val[i]+q:
            val[x]=val[i]+q
            heappush(kei,(val[x],x))
ans =0
for i in range(W):
    for j in range(H):
        if A[j][i]!=-1 and A[j][i]!=1:
            ans += val[A[j][i]]
print(ans)

Solution (Python):
from collections import Counter, deque
import heapq


def Dijkstra(C, s):
    q = []
    inf = float("inf")
    f = [inf] * 11
    f[-1] = 0
    f[s] = 0
    heapq.heappush(q, (0, s))
    while len(q) != 0:
        
        
        cost, index = heapq.heappop(q)
        if index == 1:
            return f[index]
        if f[index] < cost:
            continue
        for i in range(10):
            if cost + C[index][i] < f[i]:
                f[i] = cost + C[index][i]
                heapq.heappush(q, (f[i], i))
    return "hoge"


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

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

c = Counter()
for i in range(H):
    for j in range(W):
        c[A[i][j]] += 1
D = []
for i in range(10):
    D.append(Dijkstra(C, i))
D.append(0)
s = 0
for i, j in c.items():
    s += D[i] * j

print(s)

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

c=[None]*10

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

A=[]

for i in range(H):
    A+=list(map(int,input().split()))

minc=[None]*10

for i in range(10):
    minc[i]=c[i]



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



NUM=[0]*10

for i in range(H*W):
    if A[i]!=-1:
        NUM[A[i]]+=1

ANS=0
for i in range(10):
    ANS+=NUM[i]*minc[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)]
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 i in range(H):
  for j in range(W):
    if A[i][j]!=-1:
      ans+=c[A[i][j]][1]
print(ans)

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

cmin += [[[0]*10 for j in range(10)] for i in range(4)]

for i in range(4):
    for j in range(10):
        for k in range(10):
            cmin[i+1][j][k] = min([cmin[i][j][l] + cmin[i][l][k] for l in range(10)])

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

print(ans)

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

d = {-1: 0, 0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
for i in wall:
    for n in range(-1, 10):
        d[n] += i.count(n)
min_cost = 0
for i in range(-1, 10):
    if i == 1:
        continue
    if i == -1:
        min_cost += d[i] * costs[1][1]
    else:
        min_cost += d[i] * costs[i][1]
print(min_cost)

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

c = []
for _ 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][k] + c[k][j], c[i][j])

A = []

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

ans = 0

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

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 rA in A:
    for n in rA:
        if n >= 0:
            ans += c[n][1]

print(ans)

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

def Warshall_Floyd():
    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])

Warshall_Floyd()

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):
def main():
    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())))

    cost = [0 for _ in range(10)]
    for i in range(10):
        if i==1:
            continue
        else:
            flag = [0 for _ in range(10)] 
            flag[i] = 1
            q = [[i,0,flag],] 
            min_cost = c[i][1]
            while q != []:
                now, now_cost, now_flag = q.pop(0)
                if now==1:
                    if now_cost<min_cost:
                        min_cost = now_cost
                else:
                    for j in range(10):
                        if now_flag[j]==0 and now_cost+c[now][j]<min_cost:
                            next_flag = now_flag.copy()
                            next_flag[now] = 1
                            q.append([j,now_cost+c[now][j],next_flag])
            cost[i] = min_cost                            
    
    result = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == -1:
                result += 0
            else:
                result += cost[A[i][j]]
    return result
print(main())

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

for i in range(10):
    c = list(map(int, input().split()))
    cost.append(c)
    
dist = [[float('inf') for _ in range(10)] for _ in range(10)]
for i in range(10):
    dist[i][i] = 0
    
for s in range(10):
    next_v = [[0, s]]
    
    while len(next_v):
        v = next_v[0][1]
        for i in range(10):
            if dist[s][i] > dist[s][v] + cost[v][i]:
                dist[s][i] = dist[s][v] + cost[v][i]
                heapq.heappush(next_v, [dist[s][i], i])
        heapq.heappop(next_v)
      
mp = 0
for i in range(h):
    a = list(map(int, input().split()))
    for t in range(w):
        if a[t] != -1 and a[t] != 1:
            mp += dist[a[t]][1]

print(mp)

Solution (Python):
from collections import Counter
H,W = map(int,input().split())

d = [list(map(int,input().split())) for i in range(10)]
for i in range(10):
    d[i][i] = 10**9 
src = [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):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ctr = Counter()
for row in src:
    ctr.update(row)
ans = 0
for i in range(10):
    if i == 1: continue
    ans += ctr[i] * d[i][1]
print(ans)

Solution (Python):
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()))
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):
    B = A[i]
    for b in B:
        if b > -1:
            Ans += C[b][1]
print(Ans)

Solution (Python):
MAX = 99999999


def solve(dp):
    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])

    return dp


def m():
    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)]
    ans = [0 for _ in range(10)]
    
    c = solve(c)

    for a in A:
        for i in a:
            if i != -1:
                ans[i] += 1

    cost = 0
    for i in range(10):
        cost += c[i][1] * ans[i]
    return cost


print(m())

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

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

for l in range(h):
  tile = list(map(int, input().split()))
  for m in tile:
    if m != -1:
      ans += graph[m][1]

print(ans)

Solution (Python):
H,W = map(int,input().split())
c,A,s = [],[],0
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])
for i in range(10):
    for j in range(H):
        s += A[j].count(i) * c[i][1]
print(s)

Solution (Python):
H,W = map(int,input().split())
c,A,s = [],[],0
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])
for i in range(10):
    for j in range(H):
        s = s + A[j].count(i) * c[i][1]
print(s)

Solution (Python):
h,w = [int(i) for i in input().split()]

M = [[int(i) for i in input().split()] for j in range(10)]

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

ans = 0            
for i in range(h):
    a = [int(i) for i in input().split()]
    for j in a:
        if j == -1:
            continue
        else:
            ans += M[int(j)][1]

print(ans)

Solution (Python):
H, W = list(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 k in range(10):
    for j in range(10):
        for i in range(10):
            c[j][i] = min(c[j][i], c[j][k] + c[k][i])

ans = 0
for aa in A:
    for a in aa:
        if a == -1:
            continue
        else:
            ans += c[a][1]

print(ans)

Solution (Python):
import collections
h,w = (int(i) for i in input().split())
c = [[int(i) for i in input().split()] for i in range(10)]
a = [[int(i) for i in 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][k]+c[k][j],c[i][j])
x,answer = [],0
for i in a: x+=i
y = collections.Counter(x)
for i in range(10):
	answer += y[i]*c[i][1]
print(answer)

Solution (Python):
H,W = map(int,input().split())
cost = [[0 for x in range(10)] for y in range(10)]
for i in range(10):
  tmp = input().split()
  for j in range(10):
  	cost[i][j] = int(tmp[j])
flg = False    
number = [0]*10
for k in range(H):
  tmp = input().split()
  for l in range(W):
    if int(tmp[l]) > -1:
      number[int(tmp[l])] +=1
      flg = True

def wf():
  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])
if flg:
	wf()
sum = 0
for z in range(10):
	sum += number[z]*cost[z][1]
print(sum)

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

def dijkstra(s):
  use=[0 for i in range(10)]
  d=[1000000000000 for j in range(10)]
  d[s]=0
  while True:
    v=-1
    for i in range(10):
      if use[i]==0 and (v==-1 or d[i]<d[v]):
        v=i
    if v==-1:
      break
    use[v]=1
    for j in range(10):
      d[j]=min(d[j],d[v]+C[v][j])
  return d[1]

ans=[0 for i in range(10)]
for i in range(10):
  ans[i]=dijkstra(i)

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

Solution (Python):
from queue import PriorityQueue

def bfs(num, c):
    ans=0
    queue=PriorityQueue()
    for i in range(len(c[num])):
        if num != i:
            queue.put_nowait((c[num][i], i))


    while not queue.empty():
        node=queue.get_nowait()
        if node[1] == 1:
            return node[0]
        else:
            for num in range(len(c[node[1]])):
                if num != node[1]:
                    queue.put_nowait((node[0]+c[node[1]][num], num))

H, W=map(int, input().split())
c=[]
numList=[0 for i in range(10)]

for i in range(10):
    c.append([int(i) for i in input().split()])

for i in range(H):
    for n in input().split():
        num=int(n)
        if -1 != num and 1 != num:
            numList[num]+=1
ans=0
for i in range(len(numList)):
    if numList[i] != 0:
        ans+=bfs(i,c)*numList[i]

print(ans)

Solution (Python):


def main():
    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])

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

    print(sum(map(lambda i: c[i][1] if i >= 0 else 0, A)))

if __name__ == '__main__':
    main()