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, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
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 STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(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()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

def func(num, goto, ignore):
    if num == goto:
        return 0
    res = []
    for i in range(10):
        if i in ignore:
            continue
        nignore  = deepcopy(ignore)
        nignore.append(i)
        
        plus = func(i, goto, nignore) if d[i][goto] == -1 else d[i][goto]
        
        tmp = c[num][i] + plus
        res.append(tmp)
    return min(res)

h, w = MAP()
c = [LIST() for _ in range(10)]
a = [LIST() for _ in range(h)]
d = [[-1 for _ in range(10)] for _ in range(10)]
for i in range(10): 
    if i == 1:
        continue
    res = func(i, 1, [i])
    d[i][1] = min(c[i][1], res)
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == -1 or a[i][j] == 1:
            continue
        ans += d[a[i][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)]

from scipy.sparse.csgraph import floyd_warshall

C = floyd_warshall(C)

ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] < 0: continue
        ans += int(C[A[i][j]][1])

print(ans)

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

for k in range(10):
    for i in range(10):
        for j in range(10):
            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 wall[i][j] != -1:
            ans += C[wall[i][j]][1]
print(ans)

Solution (Python):
def warshall_floyd(c, d):
    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])
                if k == 1:
                    d[j] = c[j][k]
    return d

h, w = map(int, input().split())
c = [[int(i) for i in input().split()] for j in range(10)]
a = [[int(i) for i in input().split()] for j in range(h)]
dist = [0] * 10
ans = 0
warshall_floyd(c, dist)

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

print(ans)

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

c=[list(map(int,input().split())) for i in range(10)]
a=[list(map(int,input().split())) for i in range(h)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])
 
ans=0

for i in range(h):
    for j in range(w):
        if a[i][j]>=0:
            ans+=c[a[i][j]][1]
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    H, W = (int(i) for i in input().split())
    c = [[int(i) for i in input().split()] for j in range(10)]
    A = [[int(i) for i in input().split()] for j in range(H)]
    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra
    csr = csr_matrix(c, dtype=np.int32)
    ret = dijkstra(csr)
    ans = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == -1:
                continue
            cur = A[h][w]
            ans += int(ret[cur][1])
    print(ans)


if __name__ == '__main__':
    main()

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


def warshall_floyd(d):
    
    for k in range(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
inf=1<<32
d = [[inf for i in range(10)] for _ in range(10)]

for i in range(10):
    for j in range(10):
        d[i][j]=c[i][j]
for i in range(10):
    d[i][i] = 0 
x=warshall_floyd(d)
ans=0
for i in range(h):
    for j in range(w):
        if a[i][j]==-1:
            continue
        ans+=x[a[i][j]][1]
print(ans)

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    H,W=map(int, input().split())
    c=[list(map(int, input().split())) for _ in range(10)]
    A=[tuple(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] >= 0:
                ans += c[A[i][j]][1]
    print(ans)

if __name__ == '__main__':
    main()

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

def floyd_warshall(dist):
    v = len(dist)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

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

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

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

ans = 0
for row in A:
    for a in row:
        if a==-1: continue
        ans += C[a][1]
print(ans)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.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()
    c = LIR(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 = LIR(h)
    ans = 0
    for i in a:
        for j in i:
            if j < 0:
                continue
            ans += c[j][1]
    print(ans)
    return


if __name__ == "__main__":
    solve()

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 C[i][j] > d:
                C[i][j] = d

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

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

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


a=[list(map(int,input().split())) for _ in range(h)]
for j in a:
    for i in j:
        if i!=-1:
            ans+=dist[i][1]
print(ans)

Solution (Python):






def dijkstra(d, s, t):
    INF = 10**10
    dist = [INF] * 10
    dist[s] = 0
    checked = []

    while True:
        
        nodes = [node for node in range(10) if node not in checked]
        shortest_node, cost = nodes[0], dist[nodes[0]]

        for node in nodes:
            if dist[node] < cost:
                shortest_node, cost = node, dist[node]
        
        if shortest_node == t:
            return dist[t]

        checked.append(shortest_node)
        
        nodes = [node for node in range(10) if node not in checked]
        for node in nodes:
            dist[node] = min(
                dist[shortest_node] + d[shortest_node][node], dist[node])


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

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

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

    shortests = [None] * 10
    for s in range(10):
        if s == 1:
            shortests[s] = 0
        else:
            shortests[s] = dijkstra(c, s, 1)
    
    counts = [0] * 10
    for h in range(H):
        for w in range(W):
            if A[h][w] == -1:
                continue

            counts[A[h][w]] += 1
    
    ans = 0
    for i in range(10):
        ans += counts[i] * shortests[i]
    
    return ans


print(main())

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

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

Solution (Python):

from collections import Counter
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):
    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])

    ctr = Counter(Aij for Ai in A for Aij in Ai)
    print(sum(ctr[n] * c[n][1] for n in range(10)))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  
    c = [[int(next(tokens)) for _ in range(9 - 0 + 1)] for _ in range(9 - 0 + 1)]  
    A = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  
    solve(H, W, c, A)


if __name__ == '__main__':
    main()

Solution (Python):


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

    warshall_floyd(c)
    res = 0
    for i in range(h):
        for j in range(w):
            x = a[i][j]
            if x != -1:
                res += c[x][1]
    print(res)

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

if __name__ == "__main__":
    main()

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

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

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

for _ in range(10):
  for i in range(10):
    for j in range(10):
      if i==j:
        continue
      for k in range(10):
        if i==k or k==j:
          continue
        if c[i][k]+c[k][j]<c[i][j]:
          c[i][j]=c[i][k]+c[k][j]
          
ans=0
for i in range(h):
  for j in range(w):
    if a[i][j]==-1:
      continue
    ans+=c[a[i][j]][1]
    
print(ans)

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

for k in range(10):
  for i in range(10):
    for j in range(10):
      if S[i][j] > S[i][k] + S[k][j]:
        S[i][j] = S[i][k] + S[k][j]
        
D = {}
for i in range(H):
  line = list(map(int, input().split()))
  for j in line:
    if j in D:
      D[j] += 1
    else:
      D[j] = 1
magic = 0
for k in D:
  if k != -1:
    magic += S[k][1] * D[k]
print(magic)

Solution (Python):
from collections import Counter
def solve():
    H, W = map(int, input().split())
    C = [list(map(int, input().split())) for i in range(10)]
    A = []
    for i in range(H):
        a = list(map(int, input().split()))
        A += 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])
    
    counter = Counter(A)

    ans = 0
    for num, count in counter.items():
        if num == -1:
            continue
        ans += C[num][1] * count
    print(ans)

if __name__ == '__main__':
    solve()

Solution (Python):

from heapq import heappop, heappush

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

INF=10**11

G=[]

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

d=[INF for i in range(10)]
d[1]=0

used=[False for i in range(10)]


heap=[]
heappush(heap,(d[1],1))


while heap:
    d_u, u = heappop(heap)
    used[u] = True
    if d[u] < d_u:
        continue
    for v in range(10):
        if v==u:
            continue
        if not(used[v]) and d_u + G[v][u] < d[v]:
            d[v] = d_u + G[v][u]
            heappush(heap,(d[v],v))

ans=0

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

print(ans)

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

def warshall_floyd(d):
    
    for k in range(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

d = warshall_floyd(d) 
ans = 0 
for i in range(h):
    for j in range(w):
        if A[i][j] != 1 and A[i][j] != -1:
            ans += d[A[i][j]][1]
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline

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

graph = []
for _ in range(10):
    row = [int(i) for i in input().split()]
    graph.append(row)

def warshall_floyd(graph, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
warshall_floyd(graph, 10)
ans = 0
for _ in range(h):
    row = [int(i) for i in input().split()]
    for wall in row:
        if wall == -1 or wall == 1:
            continue
        ans += graph[wall][1]
print(ans)

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


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

cnt = 0
for i in range(H):
    for j in range(W):
        here = A[i][j]
        if here not in [-1, 1]:
            cnt += C[here][1]

print(cnt)

Solution (Python):
import heapq
import math
class Graph:
    def __init__(self,v,w_e,w_v = None):
        super().__init__()
        self.v = v

        self.w_v = w_v
        self.w_e = [{} for _ in [0]*self.v]


        self.neighbor = [[] for _ in [0]*self.v]
        for a_i,b_i,w_i in w_e:
            self.w_e[a_i][b_i] = w_i
            self.neighbor[a_i].append(b_i)

    def dijkstra(self,v_n):
        d = [10**18]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

def main():
    h,w = tuple([int(t)for t in input().split()])

    c = [[int(t) for t in input().split()]for _ in [0]*10]

    a = [[int(t) for t in input().split()]for _ in [0]*h]

    counter = [0]*10
    for a_i in a:
        for a_ij in a_i:
            if a_ij != -1:
                counter[a_ij]+=1

    w_e = []
    for i in range(10):
        for j in range(10):
            w_e.append((i,j,c[i][j]))
    
    g = Graph(10,w_e)

    routes = []
    for i in range(10):
        routes.append(g.dijkstra(i)[0])

    ans = 0
    for i in range(10):
        if i!=1:
            ans += routes[i][1]*counter[i]

    print(ans)


if __name__ == "__main__":
    main()

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

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

    dist = np.array(dijkstra(graph),dtype="int32")
    ans = 0
    for i in range(H):
        for j in c[i]:
            if j != -1:
                ans += dist[j][1] 
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
H, W = map(int, input().split())
c = [[int(j) for j in input().split()] for i in range(10)]
for i in range(10):
	for j in range(10):
		if i == j:
			continue
		for k in range(10):
			if j == k:
				continue
			if c[i][k] + c[j][i] < c[j][k]:
				c[j][k] = c[i][k] + c[j][i]
ans = 0
for i in range(H):
	A = [int(j) for j in input().split()]
	for j in A:
		if j == -1:
			continue
		ans += c[j][1]
print(ans)

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





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


warshall_floyd(C, 10)

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

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):
h,w = map(int,input().split())
c = [[int(i) for i in input().split()] for _ in range(10)]
A = {i:0 for i in range(10)}
for _ in range(h):
  for i in input().split():
    if i != '-1':
      A[int(i)] += 1
    

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(10):
  ans += c[i][1] * A[i]
print(ans)

Solution (Python):
from scipy.sparse.csgraph import dijkstra as di
from collections import Counter
h,w = map(int, input().split())

magic = [list(map(int, input().split())) for i in range(10)]
grid = Counter()
for i in range(h):
    grid.update(Counter(map(int, input().split())))



dmagic = di(magic)

ans = 0
for i in range(10):
    if i == 1 or i not in grid:
        continue
    ans += dmagic[i][1] * grid[i]

print(int(ans))

Solution (Python):
def main():
    H,W = map(int,input().split())
    cost = [[2**60]*10 for _ in range(10)]
    for i in range(10):
        cost[i][i] = 0
    for j in range(10):
        for i,c in enumerate(tuple(map(int,input().split()))):
            cost[j][i] = c
    a = [tuple(map(int,input().split()))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])
    ans = 0
    for h in range(H):
        for w in range(W):
            if a[h][w] == -1:continue
            ans += cost[a[h][w]][1]
    print(ans)

if __name__ == "__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])
cnt=0
for i in range(h):
    for j in range(w):
        if A[i][j]==-1 or A[i][j]==1:
            continue
        cnt+=C[A[i][j]][1]
print(cnt)

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

Solution (Python):
import itertools
import collections
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)]
a = list(itertools.chain.from_iterable(a))
b = collections.Counter(a)
ans = 0

def bfs(x):
    if x[-1]==1:
        global s
        buf = 0
        for i in range(len(x)-1):
            buf += c[x[i]][x[i+1]]
        s = min(s,buf)
    else:
        for i in range(10):
            if not i in x:
                bfs(x+[i])

for i in b:
    if not i in [1,-1]:
        s = 10**9
        bfs([i])
        ans += s*b[i]
print(ans)

Solution (Python):
import heapq
def dijkstra_heap(s,C):
  
  d = [float("inf")] * 10
  used = [False] * 10
  d[s] = 0
  used[s] = True
  edgelist = []
  
  
  for i,w in enumerate(C[s]):
    heapq.heappush(edgelist,[w,i]) 
  while len(edgelist):
    
    minedge = heapq.heappop(edgelist)
    
    v = minedge[1]
    if used[v]:
      continue
    d[v] = minedge[0]
    used[v] = True
    for i,w in enumerate(C[v]):
      if not used[i]:
        heapq.heappush(edgelist,[d[v]+w,i])
  return d

H, W = map(int, input().split())
C = [[] for _ in range(10)]
for i in range(10):
  c = list(map(int, input().split()))
  for j in range(10):
    C[j].append(c[j])
d = dijkstra_heap(1,C)

ans = 0
for i in range(H):
  A = list(map(int, input().split()))
  for a in A:
    if a>=0:
      ans += d[a]
print(ans)

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

ans=0
d=warshall_floyd(field)
for i in wall:
    for j in i:
        if j==-1:
            pass
        else:
            ans+=d[j][1]
print(ans)

Solution (Python):
def warshallFloyd(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

N = 10
H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(N)]
A = [list(map(int, input().split())) for _ in range(H)]
D = warshallFloyd(C)
ans = 0
ans = sum(D[A[i][j]][1] if A[i][j] != -1 else 0 for i in range(H) for j in range(W))
print(ans)

Solution (Python):
from collections import defaultdict

H,W=map(int,input().split())
dp=[[float("inf") for _ in range(10)] for _ in range(10)]
cnt = defaultdict(lambda:0)
ans=0

for i in range(10):
    tmp=tuple(map(int,input().split()))
    for k in range(10):
        dp[i][k]=tmp[k]
    dp[i][i]=0

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

for _ in range(H):
    cn=list(map(int,input().split()))
    for x in cn:
            cnt[x]+=1

for n in range(10):
    ans+=cnt[n]*dp[n][1]
print(ans)

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

for i in range(10):
    for j in range(10):
        for k in range(10):
            c[j][k] = min(c[j][k],c[j][i]+c[i][k])
ans = 0
for i in range(h):
    for j in A[i]:
        if j != -1:
            ans += c[j][1]
print(ans)

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

for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j] = min(c[i][j],c[i][k]+c[k][j])
ans = 0
for i in range(h):
    for j in A[i]:
        if j != -1:
            ans += c[j][1]
print(ans)

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
import numpy as np


h, w = map(int, input().split())
cost = [[-1 for i in range(10)] for j in range(10)]

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

cost = np.array(cost).T

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

    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):
            if d[j] > d[v]+cost[v][j]: 
                d[j] = d[v]+cost[v][j]

    return d

d = dijkstra(1,10,100,cost)
d[-1] = 0

ans = 0
for _ in range(h):
    for number in list( map(int, input().split())):
        ans += d[number]

print(ans)

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

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

def wf(table):
    from itertools import product
    for k, i, j in product(range(len(table)), repeat=3):
        table[i][j] = min(table[i][j], table[i][k] + table[k][j])

    return table

table = wf(table)

ans = 0
for _ in range(h):
    for i in map(int, input().split()):
        if i != -1:
            ans += table[i][1]

print(ans)

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

def warshall_floyd(d):
    
    for k in range(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

d = warshall_floyd(d)
ans = 0
for i in range(h):
    for j in range(w):
        if A[i][j] not in [-1, 1]:
            ans += d[A[i][j]][1]


print(ans)

Solution (Python):

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

l = [0 for _ in range(10)]
for i in a:
    for j in i:
        if j != -1:
            l[j]+=1

s = [i[1] for i in wf(c,10)]

ans = 0
for i in range(len(l)):
    if i != 1:
        ans+=s[i] * l[i]

print(ans)

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

dp = [-1] * 10
for i in range(10):
    dp[i] = list(map(int,input().split()))

for k in range(10):
    for i in range(10):
        for j in range(10):

            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

ans = 0
for _ in range(h):
    a = list(map(int,input().split()))
    for i in range(w):
        if a[i] == 1 or a[i] == -1:
            pass

        else:
            ans += dp[a[i]][1]

print(ans)