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
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
import math





















H,W = map(int,input().split())
INF = float("inf")
cost = [list(map(int,input().split())) for _ in range(10)]

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])
s = 0
for _ in range(H):
    A = list(map(int,input().split()))
    for k in A:
        if k == -1:
            continue
        s += cost[k][1]
print(s)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
import math





















H,W = map(int,input().split())
INF = float("inf")
cost = [list(map(int,input().split())) for _ in range(10)]

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])
s = 0
for _ in range(H):
    A = list(map(int,input().split()))
    for k in A:
        if k == -1:
            continue
        s += cost[k][1]
print(s)

Solution (Python):

def inputlist(): return [int(k) for k in input().split()]

def dijkstra(s,n,cost):
    
    
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True

        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

H,W = inputlist()
cost = [0]*10
for i in range(10):
    cost[i] = inputlist()
A = [0]*H
for i in range(H):
    A[i] = inputlist()

ans = 0

for x in range(H):
    for y in range(W):
        if A[x][y] == -1:
            continue
        d = dijkstra(A[x][y],10,cost)
        ans += d[1]
print(ans)

Solution (Python):
import sys

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


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

    print(ans)


if __name__ == '__main__':
    resolve()

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 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())
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
load = []
for i in range(10):
  load.append(list(map(int,input().split())))
load = np.array(load)
dist = shortest_path(load)
count = 0
for i in range (h):
  h_list = list(map(int,input().split()))
  for j in range(w):
    if h_list[j] != -1:
      count += dist[h_list[j]][1]

print(int(count))

Solution (Python):
import sys
sys.setrecursionlimit(10**6) 
import math

from copy import copy, deepcopy
from operator import itemgetter

from bisect import bisect_left, bisect, bisect_right





from collections import Counter

from itertools import accumulate

import heapq


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds




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




















tdis=[10**5]*10
dis=0


q=[(0,1)]

heapq.heapify(q)
while len(q):
    
    d, v=heapq.heappop(q)
    if tdis[v] <10**5:
        continue
    tdis[v]=d
    for i in range(10):
        heapq.heappush(q,(d+c[v][i],i))

ans=0

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

Solution (Python):
from scipy import sparse
import numpy as np
from collections import Counter
import itertools
H,W = (int(x) for x in input().split())
b = []
wall = []
ans = 0
for i in range(10):
    b.append(list(map(int, input().split())))
c = np.array(b)
w = sparse.csgraph.floyd_warshall(c)
wall = [map(int, input().split()) for _ in range(H)]
count = Counter(list(itertools.chain.from_iterable(wall)))
for item in count.items():
    if item[0] == -1:
        continue
    else:
        ans += item[1] * w[item[0]][1]
print(int(ans))

Solution (Python):
H,W = map(int,(input().split()))
c = [[] for _ in range(10)]
for i in range(10):
    c[i] = list(map(int,(input().split())))
a = [[] for _ in range(H)]
for i in range(H):
    a[i] = list(map(int,(input().split())))
        
dist = [[float("inf")]*10 for _ in range(10)]
for i in range(10):
    for j in range(10):
        dist[i][j] = c[i][j]

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

dist = warshall_floyd(dist)

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):
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
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 funci(d,j):
    ret=0
    for i in range(len(d)-1):
        ret+=c[d[i]][d[i+1]]
    ret+=c[d[-1]][j]
    return ret

def bfs(i):
    ret=c[i][1]
    todo=deque([[i,j] for j in range(10) if j!=i and j!=1])
    while len(todo)>0:
        d=todo.popleft()
        ret=min(ret,funci(d,1))
        for k in [j for j in range(10) if j not in d and j!=1]:
            f=d.copy()
            x=funci(f,k)
            if funci(f,k)<ret:
                f.append(k)
                todo.append(f)
    return ret
g=[bfs(i)for i in range(10)]
ans=0
for ai in a:
    for aij in ai:
        ans+=g[aij] if aij != -1 else 0
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])
sum = 0
for i in range(h):
    for j in range(w):
        if a[i][j] >= 0:
            sum += c[a[i][j]][1]
print(sum)

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

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

Solution (Python):
from itertools import permutations
h,w=map(int,input().split())
d=[list(map(int,input().split())) for i in range(10)]

def warshall_floyd(d):
    n=len(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
d=warshall_floyd(d)
cost=[d[i][1] for i in range(10)]

from collections import defaultdict
count=defaultdict(int)
for i in range(h):
    A=list(map(int,input().split()))
    for a in A:
        count[a]+=1

ans=0
t=[x for x in range(10) if x!=1]
for i in t:
    ans+=cost[i]*count[i]
print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
H, W = map(int, readline().split())
c = [list(map(int, readline().split())) 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])
magic = [c[i][1] for i in range(10)]
ans = 0
for _ in range(H):
    row = map(int, readline().split())
    ans += sum(magic[i] for i in row if i != -1)
print(ans)

Solution (Python):
h,w=map(int,input().split())
wlist=[list(map(int,input().split()))for _ in range(10)]
for i in range(10):
    for j in range(10):
        for k in range(10):
            wlist[j][k]=min(wlist[j][k],wlist[j][i]+wlist[i][k])
ans=0
for _ in range(h):
    t=list(map(int,input().split()))
    for i in t:
        if i==-1 or i==1:
            continue
        else:
            ans+=wlist[i][1]
print(ans)

Solution (Python):
from itertools import permutations
h,w=map(int,input().split())
es=[[] for i in range(10)]

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

n=10
import heapq

def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in es[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in es[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

cost=[dijkstra_heap(i)[1] for i in range(10)]

from collections import defaultdict
count=defaultdict(int)
for i in range(h):
    A=list(map(int,input().split()))
    for a in A:
        count[a]+=1

ans=0
t=[x for x in range(10) if x!=1]
for i in t:
    ans+=cost[i]*count[i]
print(ans)

Solution (Python):
from itertools import permutations
h,w=map(int,input().split())
C=[list(map(int,input().split())) for i in range(10)]

cost=[C[i][1] for i in range(10)]
for i in range(10):
    if i!=1:
        keiyu=[x for x in range(10) if x!=1 and x!=i]
        for j in range(9):
            perm=permutations(keiyu,r=j)
            for k in perm:
                k=[i]+list(k)+[1]
                tmp=0
                for l in range(len(k)-1):
                    tmp+=C[k[l]][k[l+1]]
                cost[i]=min(tmp, cost[i])

from collections import defaultdict
count=defaultdict(int)
for i in range(h):
    A=list(map(int,input().split()))
    for a in A:
        count[a]+=1

ans=0
t=[x for x in range(10) if x!=1]
for i in t:
    ans+=cost[i]*count[i]
print(ans)

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

def warshall_floyd(vl,d):
  
  for vk in vl:
    for vi in vl:
      for vj in vl:
        if vk in d[vi] and vj in d[vk]:
          d[vi][vj]=min(d[vi][vj],d[vi][vk]+d[vk][vj])
  return d

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


amat=[]
for i in range(H):
  amat.append([int(a) for a in input().split()])


vlist=list(range(10))
dist={}
for vi in vlist:
  dist[vi]={vi:0}
  for vj in vlist:
    dist[vi][vj]=cmat[vi][vj]


dist=warshall_floyd(vlist,dist)

    
answer=0
for i in range(H):
  for j in range(W):
    if amat[i][j]==-1:
      continue
    answer+=dist[amat[i][j]][1]
    
print(answer)

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

import heapq
def dijkstra_heap(s):
  
  dist,used={},{}
  for v in vlist:
    dist[v]=float("inf")
    used[v]=False
  dist[s]=0
  used[s]=True

  hq_edge=[]
  for v,w in edge[s]:
    heapq.heappush(hq_edge,(w,v))

  while len(hq_edge):
    min_w,min_v=heapq.heappop(hq_edge)
    
    if used[min_v]:
      continue

    dist[min_v]=min_w
    used[min_v]=True
    for v,w in edge[min_v]:
      if not used[v]:
        heapq.heappush(hq_edge,(min_w+w,v))

  return dist

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


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


vlist=list(range(10))
edge={}
for i in range(10):
  edge[i]=[]
  for j in range(10):
    edge[i].append((j,cmat[i][j]))
    
mindist=[10**9]*10
for i in range(10):
  res=dijkstra_heap(i)
  
  mindist[i]=res[1]


answer=0
for i in range(H):
  for j in range(W):
    if amat[i][j]==-1:
      continue
    answer+=mindist[amat[i][j]]
    
print(answer)

Solution (Python):
def warshalFloyd():
    G=[list(map(int,input().split())) for _ in range(10)]

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

    return G


h,w=map(int,input().split())
Graph=warshalFloyd()

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

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson,csgraph_from_dense
from scipy.sparse import csr_matrix

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

g=csr_matrix(c)
paths=shortest_path(g,method="FW")

cost=0
for i in range(h):
    for j in range(w):
        if a[i][j]!=-1 and a[i][j]!=1:
            cost+=int(paths[a[i][j]][1])

print(cost)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    
    
    

    
    
    def warshall_floyd(v_num, dist_lst):
        
        negative_cycle_flag = False

        
        
        for k in range(v_num):
            for i in range(v_num):
                for j in range(v_num):
                    
                    if dist_lst[i][k] != INF and dist_lst[k][j] != INF:
                        if dist_lst[i][j] > dist_lst[i][k] + dist_lst[k][j]:
                            dist_lst[i][j] = dist_lst[i][k] + dist_lst[k][j]

        for v in range(v_num):
            
            
            if dist_lst[v][v] < 0:
                negative_cycle_flag = True

        return dist_lst

    H, W = map(int, input().split())
    
    v_num, e_num = 10, 100

    
    
    INF = 10 ** 20
    dist_lst = [[INF] * v_num for _ in range(v_num)]

    costs = [[i for i in list(map(int, input().split()))] for _ in range(10)]
    for s in range(10):
        for t in range(10):
            dist_lst[s][t] = costs[s][t]

    dist_lst = warshall_floyd(v_num, dist_lst)
    wall = [[i for i in list(map(int, input().split()))] for _ in range(H)]
    cnt = 0
    for h in range(H):
        for w in range(W):
            val = wall[h][w]
            if val != -1:
                cnt += dist_lst[val][1]
    print(cnt)


resolve()

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

import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    H, W = map(int, input().split())

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

    dist_matrix = floyd_warshall(csgraph=graph, directed=True, return_predecessors=False)
    dist_matrix = list(dist_matrix)

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

    cnt = 0
    for h in range(H):
        for w in range(W):
            val = wall[h][w]
            if val != -1 and val != 1:
                cnt += dist_matrix[val][1]
    print(int(cnt))


resolve()

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

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

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

Solution (Python):
def dijkstra(s,n,cost):
  d=[float('inf')]*n
  visited=[0]*n
  d[s]=0
  while True:
    v=-1
    for i in range(n-1,-1,-1):
      if visited[i]==0 and v==-1:
        v=i
      elif visited[i]==0 and d[i]<d[v]:
        v=i
    if v==-1:
      break
    visited[v]=1
    for j in range(n-1,-1,-1):
      d[j]=min(d[j],d[v]+cost[j][v])
  return d

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=dijkstra(1,10,c)
ans=0
for i in range(h):
  for j in range(w):
    ans+=(cost[a[i][j]] if a[i][j]>-1 else 0)
print(ans)

Solution (Python):
import sys
import heapq
from collections import deque


INF = sys.maxsize



def main():
    ten = 10
    h,w = map(int, input().split())
    dist_mat=[]
    for i in range(ten):
        l = list(map(int, input().split()))
        dist_mat.append(l)

    table = []

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

    for k in range(ten):
        for i in range(ten):
            for j in range(ten):
                dist_mat[i][j] = min(dist_mat[i][j], dist_mat[i][k]+dist_mat[k][j])

    ans = 0
    for i in range(h):
        for t in table[i]:
            if t == -1: continue
            ans += dist_mat[t][1]


    print(ans)

if __name__ == '__main__':
    main()

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

A=[]
for h in range(H):
    a=map(int, input().split())
    A.append(a)
C=np.array(C)
D={-1:0}


def dfs(start, now,done=[]):
    next_done=done+[start]
    
    to_one=C[start,1]
    c=C[start]
    result=to_one
    for node, power in enumerate(c):
        
        if (node in next_done) or (start==node):
            continue
        if power<to_one:
            result=min(result,dfs(node,now+power, next_done)-now)
    
    return now+result
        
for i in range(10):
    done=[]
    D[i]=dfs(i,0,[])
ans=0
for h in range(H):
    a=list(map(lambda x: D[x], A[h]))
    ans+=sum(a)
    
print(ans)

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

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

converted = sum([(wf[board[h][w]][1] if board[h][w] >= 0 else 0) for w in range(W) for h in range(H)])

print(converted)

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

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

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

for i in range(h):
    line=list(map(int,input().split()))
    for l in line:
        if l==-1 or l==1:
            continue
        else:
            if l not in a:
                a[l]=1
            else:
                a[l]+=1


n=10

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

warshall_floyd()
ans=0
for num,k in a.items():
    ans+=c[num][1]*k 
print(ans)

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

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import dijkstra

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

shortest = dijkstra(c.T,indices=1)

print(shortest[a[a>-1].reshape(-1)].sum().astype(int))

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
INF = 1<<60

def resolve():
    R, C = 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):
                nc = C[i][k] + C[k][j]
                if nc < C[i][j]:
                    C[i][j] = nc

    A = [list(map(int, input().split())) for _ in range(R)]
    ans = [sum([C[x][1] if x!=-1 else 0 for x in a]) for a in A]
    print(sum(ans))

if __name__ == "__main__":
    resolve()

Solution (Python):
from collections import defaultdict

H, W = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
for w in range(10):
    for u in range(10):
        for v in range(10):
            if c[u][v] > c[u][w] + c[w][v]:
                c[u][v] = c[u][w] + c[w][v]

cost = 0
for _ in range(H):
    lv = map(int, input().split())
    for v in lv:
        if v >= 0:
            cost += c[v][1]
print(cost)

Solution (Python):
import sys
import math  
import bisect  
import queue  


def input():
    return sys.stdin.readline().rstrip()


def main():
    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 Ah in A:
        for a in Ah:
            if a != -1:
                ans += C[a][1]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def resolve():
    h, w = map(int, input().split())
    d = []
    
    for i in range(10):
        d.append(list(map(int, input().split())))
    for k in range(10):
        for i in range(10):
            for j in range(10):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    from scipy.sparse.csgraph import floyd_warshall
    cost = floyd_warshall(d)
    ans = 0
    for i in range(h):
        for j in map(int, input().split()):
            if j > -1:
                ans += cost[j][1]
    print("{:.0f}".format(ans))


resolve()

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    H,W=map(int,input().split())
    c=[list(map(int,input().split())) for _ in range(10)]
    l=[0]*10
    for _ in range(H):
        A=list(map(int,input().split()))
        for x in A:
            if x!=-1:
                l[x]+=1
    for k in range(10):
        for i in range(10):
            for j in range(10):
                c[i][j]=min(c[i][j],c[i][k]+c[k][j])
    ans=0
    for i,x in enumerate(l):
        ans+=c[i][1]*x
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
h, w = map(int, input().split())
d = []
for i in range(10):
    d.append(list(map(int, input().split())))
for k in range(10):
    for i in range(10):
        for j in range(10):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
rslt = 0
for i in range(h):
    for j in map(int, input().split()):
        if j != -1:
            rslt += d[j][1]
print(rslt)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7

H, W = map(int, input().split())
INF = 10**10
N = 10
cost = [[INF]*N for _ in range(N)]

for i in range(N):
    C = list(map(int, input().split()))
    for j in range(N):
        cost[i][j] = C[j]

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

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

print (ans)

Solution (Python):


import io
import math

nim,mike = map(int,input().split())

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

are = []

counter = 0

for _ in range(nim):
    are.extend(list(map(int,input().split())))

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

for sa in are:
    if sa != -1:
        counter += array[sa][1]

print(counter)

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
mp = [c[i][1] for i in range(10)]
mp.append(0)
for i in range(h):
    for j in range(w): ans += mp[a[i][j]]
print(ans)

Solution (Python):
from collections import Counter
H, W = map(int,input().split())
C = []
V = 10
for _ in range(V):
    C.append(list(map(int,input().split())))
for k in range(V):
    for i in range(V):
        for j in range(V):
            C[i][j] = min(C[i][j], C[i][k] + C[k][j])
A = []
for _ in range(H):
    A += list(map(int,input().split()))
count = Counter(A)
ans = 0
for i in range(V):
    ans += count[i] * C[i][1]
print(ans)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
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


cost = floyd_warshall(c)

for i in range(H):
    for j in range(W):
        if A[i][j] == -1:
            continue
        ans += cost[A[i][j]][1]
        
print(int(ans))

Solution (Python):
import heapq

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)


def dijkstra(start, goal, n, edge):
    d = [float("inf")] * n
    d[start] = 0
    q = [(0, start)]
    heapq.heapify(q)

    while q:
        ci, i = heapq.heappop(q)
        if d[i] < ci:
            continue

        for j in range(n):
            if j != start and j != i:
                if d[j] > d[i] + C[i][j]:
                    d[j] = d[i] + C[i][j]
                    heapq.heappush(q, (d[j], j))

    return d[goal]


cost = [0] * 10
for i in range(10):
    c = dijkstra(i, 1, 10, C)
    cost[i] = c

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

Solution (Python):

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

h,w = map(int,input().split())
c= []
for i in range(10):
    c.append(list(map(int,input().split())))
wf(c)
ans = 0
for i in range(h):
    for num in map(int,input().split()):
        if num==1 or num==-1:pass
        else:
            ans+=c[num][1]
print(ans)

Solution (Python):
h,w = map(int,input().split())
d = []
for i in range(10):
    a = list(map(int,input().split()))
    d.append(a)
def WF(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
WF(d)
L = []
for i in range(h):
    b = list(map(int,input().split()))
    L.append(b)
ans = 0
for i in range(h):
    for j in range(w):
        if L[i][j] == 1 or L[i][j] == -1:
            continue
        else:
            ans += d[L[i][j]][1]
print(int(ans))

Solution (Python):
def main():

    h,w = map(int,input().split())
    d = []
    for i in range(10):
        a = list(map(int,input().split()))
        d.append(a)
    def WF(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
    WF(d)
    L = []
    for i in range(h):
        b = list(map(int,input().split()))
        L.append(b)
    ans = 0
    for i in range(h):
        for j in range(w):
            if L[i][j] == 1 or L[i][j] == -1:
                continue
            else:
                ans += d[L[i][j]][1]
    print(int(ans))

if __name__ == '__main__':
	main()