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):
def calc_mp(C, d):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if k == 0:
                    d[i][j][k] = min(C[i][j], C[i][k] + C[k][j])
                else:
                    d[i][j][k] = min(d[i][j][k-1], d[i][k][k-1] + d[k][j][k-1])

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

    d = [[[0 for i in range(10)] for i in range(10)] for i in range(10)]
    calc_mp(C, d)

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

if __name__ == '__main__':
    main()

Solution (Python):
def calc_mp(C, candidates, n, ans):
    for i in range(len(candidates)):
        candidates2 = [c for c in candidates]
        c = candidates[i]
        del candidates2[i]
        a = C[n][c]
        if c != 1:
            a += calc_mp(C, candidates2, c, ans)
        ans = min(a, ans)
    return ans

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

    MPs = [0]*10
    for i in range(10):
        if i != 1:
            candidates = [j for j in range(10)]
            del(candidates[i])
            MPs[i] = calc_mp(C, candidates, i, 1000)
    
    ans = 0
    for h in range(H):
        for w in range(W):
            a = A[h][w]
            if a != -1:
                ans += MPs[a]
    print(ans)

if __name__ == '__main__':
    main()

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

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


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


a = [[0] * w for _ in range(h)]
for i in range(h):
    a[i] = list(map(int, input().split()))


arr = []
for i in range(h):
    for j in range(w):
        if a[i][j] == -1 or a[i][j] == 1:
            pass
        else:
            arr.append(a[i][j])




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(len(arr)):
    cost += c[arr[i]][1]
print(cost)

Solution (Python):





H, W = map(int, input().split())
costs = []
wall = []

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

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


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




ans = 0 
for i, line in enumerate(wall):
    for j, cell in enumerate(line):
        if cell == -1:
            continue
        ans = ans + costs[cell][1]
print(str(ans))

Solution (Python):
import sys
input = sys.stdin.readline
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)]

def dfs(i, j) :
    magi = c[i][1] + j
    for k in range(10) :
        if visited[k] == 0 and c[i][k] < c[i][1] :
            visited[k] = 1
            magi = min(magi, dfs(k, c[i][k] + j))
            visited[k] = 0
    return magi

ans = [10**5 for _ in range(10)]
for i in range(10) :
    visited = [0 for _ in range(10)]
    visited[i] = 1
    ans[i] = dfs(i, 0)

ans2 = 0
for ai in A :
    for aii in ai :
        if aii == -1 :
            continue
        else :
            ans2 += ans[aii]

print(ans2)

Solution (Python):
H,W = map(int,input().split())
C = []
for _ in range(10):
  List = list(map(int,input().split()))
  C.append(List)
Wall = []
for _ in range(H):
  List = list(map(int,input().split()))
  Wall.append(List)
for k in range(10):
  for i in range(10):
    for j in range(10):
      if i != j:
        C[i][j] = min(C[i][j],C[i][k]+C[k][j])
      else:
        C[i][j] = 0
Answer = 0
for line in Wall:
  for item in line:
    if item!= -1:
      Answer += C[item][1]
print(Answer)

Solution (Python):
H, W = map(int, input().split())
C = [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 = C[i][k] + C[k][j]
            if d < C[i][j]:
                C[i][j] = d

ans = 0
cost = [C[i][1] for i in range(10)]

for _ in range(H):
    for n in map(int, input().split()):
        if n == -1:
            continue
        ans += cost[n]

print(ans)

Solution (Python):
h,w=map(int,input().split())
G=[[0]*10 for i in range(10)]
for i in range(10):
  G[i]=list(map(int,input().split()))
A=[1,2,6,24,120,720,5040,40320]
B=[i for i in range(10)]
E=[0]*10
for i in range(10):
  if i==1:
    continue
  E[i]=10**10
  for j in range(362880):
    C=B[0:11]
    D=[i]
    C.remove(i)
    for k in range(8):
      a=j//A[-1-k]
      j=j-A[-1-k]*a
      b=C.pop(a)
      D.append(b)
      if b==1:
        break
    D.append(C[0])
    c=0
    for j in range(9):
      if D[j]==1:
        break
      c=c+G[D[j]][D[j+1]]
    if c<E[i]:
      E[i]=c
F=[0]*11
GG=[[0]*w for i in range(h)]
for i in range(h):
  GG[i]=list(map(int,input().split()))
  for j in range(w):
    F[GG[i][j]]=F[GG[i][j]]+1
ans=0
for i in range(10):
  ans=ans+E[i]*F[i]
print(ans)

Solution (Python):
from collections import Counter

h , w = map(int , input().split())
c = [[] for _ in range(10)]
a = [[] for _ in range(h)]
b = Counter()
for i in range(10):
    c[i] = list(map(int,input().split()))
    
for i in range(h):
    a[i] = list(map(int,input().split()))
    b += Counter(a[i])
    
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(10):
    ans += (c[i][1] * b[i] )
    
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

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
h, w = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
n = 10
Warshall_Floyd(c)

A =[list(map(int, input().split())) for _ in range(h)]
S = []
S_append = S.append
for a in A:
    for i in a:
      if i != -1 and i != 1:
        S_append(i)
ans = 0
for s in S:
  ans += c[s][1]
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

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
h, w = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
n = 10
Warshall_Floyd(c)

A =[list(map(int, input().split())) for _ in range(h)]
S = []
S_append = S.append
for a in A:
    for i in a:
      if i != -1 and i != 1:
        S_append(i)
ans = 0
for s in S:
  ans += c[s][1]
print(ans)

Solution (Python):
from collections import deque
import sys
input = lambda: sys.stdin.readline().rstrip()

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

c_list = []

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


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

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

print(ans)

Solution (Python):
h, w = map(int, input().split())
c = [[int(i) for i in input().split()] for _ in range(10)]
a = [[int(i) for i in 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 a_ in a:
    for ai in a_:
        if ai == 1 or ai == -1: continue
        else: ans += c[ai][1]
print(ans)

Solution (Python):
n = 10
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
H, W = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
d = warshall_floyd(c)
ans = 0
for _ in range(H):
    tmp = list(map(int, input().split()))
    for i in tmp:
        if i == -1:
            continue
        ans += c[i][1]
print(ans)

Solution (Python):
H, W = map(int, raw_input().split())
c = []

for i in range(10):
    ci = map(int, raw_input().split())
    c.append(ci)

A = []

for i in range(H):
    ai = map(int, raw_input().split())
    A.append(ai)


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

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

print ans

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    h,w = LI()
    d = LIR(10)
    for k in range(10):
        for i in range(10):
            for j in range(10):
                nd = d[i][k]+d[k][j]
                if nd < d[i][j]:
                    d[i][j] = nd
    a = LIR(h)
    ans = 0
    for i in a:
        for j in i:
            if j < 0:
                continue
            ans += d[j][1]
    print(ans)
    return


if __name__ == "__main__":
    solve()

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

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

def dfs(i, v):
    if i == 1:
        return v
        
    min_v = int(1e9)
    for j in range(10):
        if f[j] == False:
            f[j] = True
            min_v = min(min_v, v + dfs(j, m[i][j]))
            f[j] = False
            
    return min_v
    
min_vs = [-1] * 10
for i in range(10):
    f = [False] * 10
    f[i] = True
    min_vs[i] = dfs(i, 0)
min_vs += [0]
    
v = 0
for _ in range(H):
    v += sum(list(map(lambda x: min_vs[int(x)], input().rstrip().split()))) 
print(v)

Solution (Python):

import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

def disktra(g,s):
    n=len(g)
    dist = [inf]*n
    dist[s] = 0
    hq=[]
    heapq.heappush(hq,(dist[s],s))
    while hq:
        cost,u =heapq.heappop(hq)
        if dist[u] < cost:
            continue
        for v,c in g[u]:
            if dist[v] <= dist[u] +c:
                continue
            dist[v] = dist[u] + c
            heapq.heappush(hq,(dist[v],v))
    return dist

h,w = map(int,input().split())
C = [list(map(int,input().split())) for i in range(10)]
G = [[] for i in range(10)]
for i,ci in enumerate(C):
  for j,vj in enumerate(ci):
    G[j].append((i,vj))
dist = disktra(G,1)
for i in range(h):
  for number in map(int,input().split()):
    if number == -1: continue
    ans += dist[number]
print(ans)

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

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

print(ans)

Solution (Python):
H, W = map(int, input().split())
costs = []
wall = []

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

total_cost = 0

for i in range(H):
  for j in range(W):
    n = wall[i][j]
    if n == -1:
      continue
    total_cost += costs[n][1]
    
print(total_cost)

Solution (Python):
h,w = map(int, input().split())
c = []
for i in range(10):
  arr = list(map(int, input().split()))
  c.append(arr)
  
a = []
for i in range(h):
  arr = list(map(int, input().split()))
  a.append(arr)
  
for i in range(10):
  arr = c[i]
  kakutei = [False] * 10
  kakutei[i] = True

  kakutei_num = 1
  while kakutei_num != 10:
    min_num = 1000000
    index = -1
    for j in range(10):
      if not kakutei[j] and min_num > arr[j]:
        min_num = min(min_num, arr[j])
        index = j
      
    kakutei[index] = True
    kakutei_num += 1
    for j in range(10):
      c[i][j] = min(c[i][j], c[i][index] + c[index][j])
      
ans = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == -1:
      continue
    
    n = a[i][j]
    ans += c[n][1]
'''    
for i in range(len(c)):
  print(c[i])
'''
print(ans)

Solution (Python):
def main():
    height, width = map(int, input().split())
    change_cost = [list(map(int, input().split())) for _ in range(10)]
    grid = [list(map(int, input().split())) for _ in range(height)]
    for k in range(10):
        for i in range(10):
            for j in range(10):
                change_cost[i][j] = min(change_cost[i][j], change_cost[i][k] + change_cost[k][j])
    answer = 0
    for g in grid:
        for n in g:
            if abs(n) != 1:
                answer += change_cost[n][1]
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
from scipy.sparse.csgraph import shortest_path
import numpy as np
H,W = [int(i) for i in input().split()]
c = [0] * 10
for i in range(10):
    c[i] = [int(j) for j in input().split()]
c = np.array(c)
path = shortest_path(c,'D')
A = [0] * H
for i in range(H):
    A[i] = [int(j) for j in input().split()]
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == 1 or A[i][j] == -1:
            continue
        ans += path[A[i][j]][1]
print(int(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)]

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

G = np.array(c)
dist = floyd_warshall(G)


ans = 0
for i in range(h):
    for j in range(w):
        ai = a[i][j]
        if ai == -1:
            continue
        ans += dist[ai][1]
print(int(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)]

def warshall_floyd(d, v):
    for k in range(v):
        for i in range(v):
            for j in range(v):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
            
warshall_floyd(c, 10)
res = 0
for i in range(h):
    for j in range(w):
        if a[i][j] != -1:
            res += c[a[i][j]][1]
print(res)

Solution (Python):
import sys
input = sys.stdin.readline
def readlines(n):
    for _ in range(n):
        yield list(map(int, input().split()))

def main():
    h, w = map(int, input().split())

    C = list(readlines(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])

    for line in readlines(h):
        yield sum(C[c][1] for c in line if c != -1) 


print(sum(main()))


main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter
from itertools import chain

def readlines(n):
    for _ in range(n):
        yield map(int, input().split())

def main():
    h, w = map(int, input().split())

    C = [[int(c) for c 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])

    counter = Counter(chain(*readlines(h)))

    for i in range(10):
        yield C[i][1] * counter[i]


print(sum(main()))


main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter
from itertools import chain

def readlines(n):
    for _ in range(n):
        yield map(int, input().split())

def main():
    h, w = map(int, input().split())

    C = list(map(list, readlines(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])

    counter = Counter(chain(*readlines(h)))

    for i in range(10):
        yield C[i][1] * counter[i]


print(sum(main()))


main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter
from itertools import chain

def readlines(n):
    for _ in range(n):
        yield list(map(int, input().split()))

def main():
    h, w = map(int, input().split())

    C = list(readlines(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])

    c = Counter(chain(*readlines(h)))

    for i in range(10):
        yield C[i][1] * c[i]


print(sum(main()))


main()

Solution (Python):
h, w = 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 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:
            ans += c[a[i][j]][1]
        else:
            continue
print(ans)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

N,M = m()

po = [l() for i in range(10)]

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


num = [0 for i in range(10)]

co = 0

for i in range(N):
    aaa = l()
    for j in aaa:
        if j != -1:
            num[j] += 1

for i in range(10):
    if i != 1:
        co += po[i][1] * num[i]
print(co)

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)]
dp = [[10 ** 4 for _ in range(10)] for _ in range(10)]
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])
b = [0] + [c[i][1] for i in range(10)]
ans = 0
for i in a:
    for j in i:
        ans += b[j + 1]
print(ans)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians

from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    H, W = MAP()
    C = [LIST() for _ in range(10)]
    A = [LIST() 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 h in range(H):
        for w in range(W):
            if A[h][w] != -1:
                ans += C[A[h][w]][1]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
C = []
for i in range(10):
    tmp = LIST()
    C.append(tmp)
A = []
for i in range(H):
    tmp = LIST()
    A.append(tmp)
    

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

C = warshall_floyd(C, 10)

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):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from heapq import heappop, heappush

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist


H, W = MAP()
C = [LIST() for i in range(10)]
A = [LIST() for i in range(H)]

graph = defaultdict(list)

for i in range(10):
    for j in range(10):
        cost = C[i][j]
        graph[i].append((j, cost))

ans = 0
for i in range(H):
    for j in range(W):
        from_num = A[i][j]
        if from_num == -1:
            continue
        elif from_num == 1:
            continue
        else:
            ans += dijkstra(graph, from_num)[1]
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
cost = [LIST() for _ in range(10)]
wall = [LIST() for _ in range(H)]

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

magic = 0
for i in range(H):
	for j in range(W):
		if wall[i][j] == -1:
			pass
		else:
			magic += cost[wall[i][j]][1]

print(magic)

Solution (Python):
'''
https://atcoder.jp/contests/abc079/tasks/abc079_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

    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)]
    N = 10
    for k in range(N):
        for i in range(N):
            for j in range(N):
                c[i][j] = min(c[i][j], c[i][k]+c[k][j])
    res = 0
    for i in A:
        for j in i:
            if j == -1:
                continue
            res += c[j][1]
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
h, w = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(10)]
for i in range(10):
    for j in range(10):
        for k in range(10):
            magic[j][k] = min(magic[j][k], magic[j][i]+magic[i][k])

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

print(ans)

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()

from scipy.sparse.csgraph import floyd_warshall
h,w=map(int,input().split())
table=[]
for i in range(10):
  table.append([int(i) for i in input().split()])
d=floyd_warshall(csgraph=table, directed=True, return_predecessors=False)

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

Solution (Python):
import numpy as np
H, W = map(int, input().split())

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


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