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):
import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline
import math
from heapq import heappush, heappop

def solve(h,w,tables,A):
  for i in range(10):
    for j in range(10):
      for k in range(10):
        tables[j][k] = min(tables[j][k], tables[j][i] + tables[i][k])
  cost = 0
  for i in range(h):
    for j in range(w):
      p = A[i][j]
      if p == -1:
        continue
      cost += tables[p][1]
  return cost
  

def main():
  h, w = map(int, input().split(' '))
  tables = []
  for i in range(10):
    tables.append(list(map(int, input().split(' '))))
  A = []
  for _ in range(h):
    A.append(list(map(int, input().split(' '))))
  ans = solve(h, w, tables, A)
  print(ans)
  

if __name__=='__main__':
  main()

Solution (Python):

from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
import math
sys.setrecursionlimit(10**6)




def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]


H, W = zz()
C = []
for i in range(10):
    C.append(zz())
A = []
num_lis = [0]*10
for i in range(H):
    a = zz()
    for a_ in a:
        if (a_ == -1):
            continue
        num_lis[a_] += 1
    A.append(a)




a = floyd_warshall(C)
ans = 0
for i, num in enumerate(num_lis):
    ans += a[i, 1]*num
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 main():
    for k in range(10):
        for i in range(10):
            for j in range(10):
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])

    print(
        sum(
            c[a][1] for column in A for a in column if a >= 0 
        )
    )


if __name__ == "__main__":
    main()

Solution (Python):
H, W = map(int, input().split())
cost = [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):
            cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
            
ans = 0
for i in range(H):
    for j in range(W):
        now = A[i][j]
        if now != -1:
            ans += cost[now][1]
            
print(ans)

Solution (Python):
H,W = map(int,input().split())
inf=10**10
n=10

e = [[inf]*n for _ in range(n)]

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





cost=[inf]*10


def dijkstra(s):
    color=["WHITE"]*n
    d=[inf]*n
    p=[-1]*n
    d[s]=0
    p[s]=-1
    while True:
        mincost =inf
        for i in range(n):
            if color[i] !="BLACK" and d[i] < mincost:
                mincost =d[i]
                u=i
        if mincost ==inf:
            break
        color[u]="BLACK"
        
        for v in range(n):
            if color[v] !="BLACK" and e[u][v] !=inf:
                if d[u] +e[u][v] <d[v]:
                    d[v]=d[u] +e[u][v]
                    p[v]=u
                    color[v] ="GRAY"
    return d[1]
ans=10**10

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



goukei=0
for i in range(10):
    if i!=1:
        ret=dijkstra(i)

        goukei+=ret*T[i]
print(goukei)

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

h,w=map(int,input().split())
DP=[list(map(int,input().split())) for i in range(10)]

table=warshall_floyd(DP)

cnt=[]
ans=0

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


for i in cnt:
  if i==-1:
    continue
  ans+=table[i][1]


print(ans)

Solution (Python):
from collections import deque
import sys, copy, itertools,heapq
input = sys.stdin.readline

h,w = map(int,input().split())
TRANS = [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 (TRANS[i][k] != float('inf')) and (TRANS[i][k] != float('inf')):
        TRANS[i][j] = min(TRANS[i][j],TRANS[i][k] + TRANS[k][j])


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

print(ans)

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

INF = float('inf')
for k in range(V):
    for i in range(V):
        for j in range(V):
            if cost[i][k]!=INF and cost[k][j]!=INF:
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

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

Solution (Python):
N = 10
H, W = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(N)]
A = [list(map(int, input().split())) for _ in range(H)]
for h in range(N):
    for w in range(N):
        if g[h][w] == 0:
            g[h][w] = float('inf')

for k in range(N):
    for i in range(N):
        for j in range(N):
            g[i][j] = min(g[i][j], g[i][k]+g[k][j])

ans = 0
for h in range(H):
    for w in range(W):
        if abs(A[h][w]) != 1:
            ans += g[A[h][w]][1]

print(ans)

Solution (Python):
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    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):
                if c[i][j] > c[i][k] + c[k][j]:
                    c[i][j] = c[i][k] + c[k][j]

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

    print(ans)

main()

Solution (Python):
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    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):
                if c[i][j] > c[i][k] + c[k][j]:
                    c[i][j] = c[i][k] + c[k][j]

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

    print(ans)

main()

Solution (Python):
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]


def main():
    H, W = MI()
    D = defaultdict(int)
    
    cost = [LI() for i in range(10)]
    
    for i in range(H):
        temp = LI()
        for j in temp:
            if j != -1:
                D[j]+=1

    for i in range(10):
        for j in range(10):
            for k in range(10):
                cost[j][k] = min(cost[j][k], cost[j][i]+cost[i][k])
                
    ans = 0
    
    for key, num in D.items():
        ans += cost[key][1]*num
        
    print(ans)

    
if __name__ == "__main__":
    main()

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


def main():
    input = sys.stdin.buffer.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)]
    d = floyd_warshall(csgraph=csr_matrix(c, dtype="i8"), directed=True)
    ans = 0
    for n in itertools.chain.from_iterable(a):
        if n != -1:
            ans += int(d[n][1])
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    h,w = i_map()
    c = [i_list() for i in range(10)]

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

    ans = 0
    for h in range(h):
        a = i_list()
        for b in a:
            if b>=0:
                ans += c[b][1]
    print(ans)



if __name__=="__main__":
    main()

Solution (Python):
"""
きょうぎぷろぐらみんぐ！！！！！！
競プロ競プロ競プロ競プロ競プロ競プローーーーー！！！！！！！
hshs！！ﾊｱﾊｱ！！興奮興奮！！！！うおおおおおおお！！！
競プロの重要性！！ｺﾞﾝｺﾞﾝｺﾞﾝｺﾞﾝ(頭を難易度の壁に打ち付ける音)
うおおおおおおお！！競プロの重要性！！
"""
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
h,w=map(int,input().split())
num=[list(map(int,input().split())) for _ in range(10)]
num=csr_matrix(num)
ans=shortest_path(num)
ans=ans.tolist()
ans2=[0]*10
for i in range(10):
    ans2[i]=int(ans[i][1])
ans3=0
for i in range(h):
    a=list(map(int,input().split()))
    for j in range(w):
        if a[j]!=-1:
            ans3+=ans2[a[j]]
print(ans3)

Solution (Python):
import sys
input = sys.stdin.readline
if __name__ == "__main__":
    H,W = map(int,input().split())
    V = 10
    edges = []
    for i in range(10):
        c = list(map(int,input().split()))
        edges.append([(j,c[j]) for j in range(10)])
    INF = float("inf")
    dp = [[INF]*V for _ in range(V)]
    for i in range(V):
        for j, w in edges[i]:
            dp[i][j] = w

    for k in range(V):
        for i in range(V):
            for j in range(V):
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
    ans = 0
    for _ in range(H):
        for x in map(int,input().split()):
            if x >= 0:
                ans += dp[x][1]
    print(ans)

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

def w_f(C):
    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])
    return C

C = w_f(C)

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

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):
from numpy import *
from scipy.sparse.csgraph import *
H,W = map(int,input().split())
G = array([list(map(int,input().split())) for n in range(10)])
A = [list(map(int,input().split())) for h in range(H)]
F = shortest_path(G)
ans = 0

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

print(int(ans))

Solution (Python):
INF=float('inf')
h,w=map(int,input().split())
dist=[[0 for i in range(10)]for j in range(10)]
for i in range(10):
  s=list(map(int,input().split()))
  for j in range(10):
    if i==j:
      continue
    dist[i][j]=s[j]

for k in range(10):
  for i in range(10):
    for j in range(10):
      dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
ans=0
for i in range(h):
  T=list(map(int,input().split()))
  for j in range(w):
    if T[j]==-1:
      continue
    if T[j]==1:
      continue
    ans+=dist[T[j]][1]
print(ans)

Solution (Python):
H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(10)]
for i in range(10):
    for k in range(10):
        for l in range(10):
            C[k][l] = min(C[k][l], C[k][i]+C[i][l])
ans = 0
for _ in range(H):
    k = list(map(int, input().split()))
    for i in k:
        if i == -1:
            continue
        ans += C[i][1]
print(ans)

Solution (Python):

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


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

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

Solution (Python):


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

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

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

res = 0
for h in range(H):
    A = list(map(int, input().split()))
    for a in A:
        if a != -1:
            res += edge[a][1]

print(res)

Solution (Python):
import numpy as np
H, W = (int(x) for x in input().split())
C = np.array([[int(x) for x in input().split()] for _ in range(10)])
A = [[int(x) if int(x) >= 0 else 1 for x in input().split()] for _ in range(H)]
from scipy.sparse.csgraph import dijkstra
C = dijkstra(C,directed=True) 
ans = sum(sum(C[x,1] for x in A))
print(int(ans))

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

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

d = copy(data)
def cnt_set(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])
cnt_set(d)
ans = 0

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

print(ans)

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

for k in range(10):
  for i in range(10):
    for j in range(10):
      mp[i][j] = min(mp[i][j], mp[i][k]+mp[k][j])
    
rlt = 0
for i in range(H):
  for j in map(int, input().split()):
    if j != -1 and j != 1:
      rlt += mp[j][1]
      
print(rlt)

Solution (Python):
from collections import Counter
H,W=list(map(int, input().split()))
C=[list(map(int, input().split())) for _ in range(10)]
A=Counter()
for _ in range(H):
    A+=Counter(list(map(int, input().split())))
del A[-1]



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


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

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

H,W = I()
cost = [l() for _ in range(10)]
A = [l() for _ in range(H)]
ans = 0
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])
for i in range(H):
    for j in range(W):
        if A[i][j] > -1:
            ans += cost[A[i][j]][1]
print(ans)

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





def wf_func(mat):
    dist = mat
    for k in range(10):
        for i in range(10):
            for j in range(10):
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
    return dist





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

Solution (Python):
"""ABC079D Wall 別解
ワーシャルフロイドでやった場合
"""

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

counter = {i: 0 for i in range(-1, 10)}
for i in range(H):
    tmp = list(map(int, input().split()))
    for j in range(W):
        counter[tmp[j]] += 1

dp = c.copy()
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 = sum([counter[i]*dp[i][1] for i in range(10)])
print(ans)

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

counter = {i: 0 for i in range(-1, 10)}
for i in range(H):
    tmp = list(map(int, input().split()))
    for j in range(W):
        counter[tmp[j]] += 1
MAX = 10**4
INF = float("inf")
def f(start):
    if start == 1:
        return 0
    dp = [[INF]*MAX for _ in range(10)]
    dp[start][0] = 0
    for i in range(1, MAX):
        for new in range(10):
            dp[new][i] = min(dp[num][i-1] + c[num][new] for num in range(10))
    return min(dp[1])

ans = 0
for i in range(10):
    if counter[i] == 0:
        continue
    else:
        ans += counter[i] * f(i)
print(ans)

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

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

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

Solution (Python):
H,W=map(int,input().split())
weight=[list(map(int,input().split())) for _ in range(10)]
graph=[[i for i in range(10)] for j in range(10)]
for i in range(10):
  graph[i].pop(i)
import math
import heapq

d=[math.inf for i in range(10)]
d[1]=0
q=[]
heapq.heappush(q,1)
while q:
  v=heapq.heappop(q)
  for u in graph[v]:
    if weight[u][v]+d[v]<d[u]:
      d[u]=weight[u][v]+d[v]
      heapq.heappush(q,u)
A=[list(map(int,input().split())) for _ in range(H)]

dic={}
for i in range(H):
  for j in range(W):
    if A[i][j]!=-1:
      if A[i][j] in dic:
        dic[A[i][j]]+=1
      else:
        dic[A[i][j]]=1
ans=0
for k,v in dic.items():
  ans+=d[k]*v
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):
            C[i][j] = min(C[i][j], C[i][k] + C[k][j])
ans=0
for aa in A:
    for a in aa:
        if a==-1:
            ans+=0
        else:
            ans+=C[a][1]
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline
H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in [0]*10]
A = map(int, read().split())

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

cnt = [0]*10
for a in A:
    if a != -1:
        cnt[a] += 1
ans = 0
for i, c in enumerate(cnt):
    ans += C[i][1] * c
print(ans)

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

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


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

count = 0
for i in range(H):
    for j in range(W):
        if (A[i][j] == -1):
            continue
        else:
            count += C[A[i][j]][1]

print(count)

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

power = warshall_floyd(power)

ans = 0
for i in range(h):
    wall = list(map(int, input().split()))  
    for key in wall:
        if key == -1:
            continue
        ans += power[key][1]
print(ans)

Solution (Python):
from heapq import heappop, heappush

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


INF = 10**12
q = [(0,1)] 
d = [INF] * 10
d[1] = 0

while len(q) > 0:
    cost, u = heappop(q)
    
    for v in range(10):
        if v == u: continue
        
        tmp = d[u] + c[v][u]
        
        if tmp < d[v]:
            d[v] = tmp
            heappush(q, (d[v], v))
    

A =  [0]*10
for i in range(H):
    tmp = list(map(int, input().split()))
    for j in range(W):
        if tmp[j] >= 0:
            A[tmp[j]] += 1

ans = 0
for i in range(10):
    ans += A[i]*d[i]
print(ans)

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



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):
  temp = list(map(int,input().split()))
  for j in range(W):
    if temp[j] == -1:
      continue
    ans += c[temp[j]][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)]
dist = [[0 for _ in range(10)] for _ in range(10)]
for i in range(10):
    for j in range(10):
        dist[i][j] = C[i][j]
for k in range(10):
    for i in range(10):
        for j in range(10):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
cnt = 0
for i in range(H):
    for j in range(W):
        if A[i][j]>=0:
            cnt += dist[A[i][j]][1]
print(cnt)

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

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

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

ans = 0
for i in range(h):
    ans += sum(map(lambda x: g[x][1],
                   filter(lambda x: x != -1, map(int, input().split()))))
print(ans)

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


h,w = map(int, input().split())
cl = [list(map(int, input().split())) for _ in range(10)]
cl = warshall_floyd(cl,10)

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

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

                
from collections import Counter

INF = float('inf') 
H, W = map(int, input().split())
d =[[int(i) for i in input().split()] for _ in range(10)]  
a = []
for _ in range(H):
    a.extend([int(i) for i in input().split() if i != '-1'])
dic = Counter(a)     

warshall_floyd(10)   

ans = 0
for key, val in dic.items():
    ans += d[key][1] * val   

print(ans)

Solution (Python):
from itertools import chain
import numpy as np
import networkx as nx

h, w, *X = map(int, open(0).read().split())
C = np.array(X[:100], dtype=int).reshape((10, 10))
A = np.array(X[100:], dtype=int).reshape((h, w))

G = nx.DiGraph(C)
d = {-1:0}
for i in range(10):
    d[i] = nx.shortest_path_length(G, i, 1, weight='weight')
print(sum(d[a] for a in chain.from_iterable(A)))

Solution (Python):
from itertools import chain
import numpy as np
import networkx as nx

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
C = np.zeros((10, 10), dtype=int)
for i in range(10):
    for j, c in enumerate(map(int, next(X).split())):
        C[i, j] = c
A = np.zeros((h, w), dtype=int)
for i in range(h):
    for j, a in enumerate(map(int, next(X).split())):
        A[i, j] = a

G = nx.DiGraph(C)
d = {-1:0}
for i in range(10):
    d[i] = nx.shortest_path_length(G, i, 1, weight='weight')
print(sum(d[a] for a in chain.from_iterable(A)))

Solution (Python):
from itertools import chain
import numpy as np
import networkx as nx

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
C = np.zeros((10, 10), dtype=int)
for i in range(10):
    for j, c in enumerate(map(int, next(X).split())):
        C[i, j] = c
A = np.zeros((h, w), dtype=int)
for i in range(h):
    for j, a in enumerate(map(int, next(X).split())):
        A[i, j] = a

G = nx.DiGraph(C)
d = {}
for i in range(10):
    if i == 1:
        continue
    d[i] = nx.shortest_path_length(G, i, 1, weight='weight')

s = 0
for a in chain.from_iterable(A):
    if a == -1 or a == 1:
        continue
    s += d[a]
print(s)

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

inf = 10 ** 20
d = [list(map(int, input().split())) for _ in range(10)]

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

ans = 0
for _ in range(h):
    row = list(map(int, input().split()))
    for num in row:
        if num == -1:
            continue
        ans += d[num][1]

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')




import numpy as np    




def solve():
    H, W = MI()
    dist = LLI(10)
    N = 10

    
    
    

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = 0
    for i in range(H):
        for r in LI():
            if r != -1:
                ans += dist[r][1]
    print(ans)




if __name__ == '__main__':
    solve()

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

cost = [[float("inf")]*10 for _ in range(10)]



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


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

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

Solution (Python):
def warshall_floyd():
    for middle in range(10):
        for start in range(10):
            for end in range(10):
                costs[start][end] = min(costs[start][end], costs[start][middle] + costs[middle][end])


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

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

warshall_floyd()


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