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

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

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

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

Solution (Python):
import heapq

H,W = map(int,input().split())
edges = [{}for _ in range(10)]
for i in range(10):
    l = list(map(int,input().split()))
    for j in range(10):
        if j != i:
            edges[j][i] = l[j]
costDic = {}
que = [(0,1)]
heapq.heapify(que)
while que:
    cost,now = heapq.heappop(que)
    if now not in costDic:
        costDic[now] = cost
        for nx,c in edges[now].items():
            if nx not in costDic:
                heapq.heappush(que,(cost+c,nx))

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

print(ans)

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

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



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


cost = 0
for _ in range(H):
    nums = list(map(int, input().split()))
    for num in nums:
        if num == -1:
            cost += 0
        else:
            cost += change_costs[num][1]
    
print(cost)

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

H, W = map(int, input().split())
C = [[int(i) for i in input().split()] for _ in range(10)]
A = []
for _ in range(H):
    A += [int(i) for i in input().split()]
D = dijkstra(C)
D = D[:, 1]
ans = 0
for x in A:
    if abs(x) != 1:
        ans += int(D[x])
print(ans)

Solution (Python):

import sys


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])
    
    cost = 0
    for a in A:
        for aa in a:
            if aa == -1:
                continue
            cost += c[aa][1]
    return cost



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)]  
    print(solve(H, W, c, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):

import sys


def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):
    
    for _ in range(10):
        for i in range(10):
            for j in range(10):
                for k in range(10):
                    c[i][j] = min(c[i][j], c[i][k]+c[k][j])
    
    cost = 0
    for a in A:
        for aa in a:
            if aa == -1:
                continue
            cost += c[aa][1]
    return cost



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)]  
    print(solve(H, W, c, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):
import sys
import heapq


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


def dijkstra(start, n_nodes, edge):
    dist = [float("inf")] * n_nodes
    dist[start] = 0
    
    q = [(dist[start], start)]
    heapq.heapify(q)
    while q:
        
        d, i = heapq.heappop(q)
        
        
        if dist[i] < d:
            continue
        
        
        for cost, j in edge[i]:
            if dist[j] > dist[i] + cost:
                dist[j] = dist[i] + cost
                heapq.heappush(q, (dist[j], j))
    return dist


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


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

    D = [dijkstra(i, 10, edge) for i in range(10)]
    answer = 0
    for _ in range(H):
        A = list(map(int, input().split()))
        for w in range(W):
            if A[w] != -1:
                answer += D[A[w]][1]
    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline

INF = float("inf")


def warshall_floyd(n, d):
    for k in range(n):
        for i in range(n):
            d_ik = d[i][k]
            if d_ik == INF:
                continue
            for j in range(n):
                if d[i][j] > d_ik + d[k][j]:
                    d[i][j] = d_ik + d[k][j]


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

    warshall_floyd(10, c)

    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)


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
import heapq


H, w = map(int, input().split())
cost = np.zeros((10, 10), dtype=np.int64)
for i in range(10):
    temp = map(int, input().split())
    for j, x in enumerate(temp):
        cost[j, i] = x
d = np.zeros(10, dtype=np.int64)
h = []
heapq.heappush(h, (0, 1))
while h:
    dx, x = heapq.heappop(h)
    for y in range(10):
        if y in [1, x]:
            continue
        if d[y] == 0 or dx + cost[x, y] < d[y]:
            d[y] = dx + cost[x, y]
            heapq.heappush(h, (d[y], y))
ans = 0
for _ in range(H):
    row = input().split()
    for x in row:
        x = int(x)
        ans += 0 if x == -1 else d[x]
print(ans)

Solution (Python):
from collections import Counter

H,W = map(int,input().split())
dp = [[0]*10 for _ in range(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])
      
el = []
for i in range(H):
  el += list(map(int,input().split()))
  
S=Counter(el)
r = 0
for i in range(10):
  r += S[i]*dp[i][1]
  
print(r)

Solution (Python):
from collections import Counter
h,w = map(int,input().split())
n=10
c_input = [list(map(int,input().split())) for i in range(10)]
a_input = [int(j) for i in range(h) for j in input().split() if int(j)!=-1]

a_count = Counter(a_input)

dp=[[float('inf') for i in range(n)]for i in range(n)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            c_input[i][j] = min(c_input[i][j],c_input[i][k]+c_input[k][j])
ans=0
for k,v in a_count.items():
    ans+=c_input[k][1]*v
print(ans)

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

h, w = map(int, input().split())
n = 10
dist = dijkstra([list(map(int, input().split())) for _ in range(n)])

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

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

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

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

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

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

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

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

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

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

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

from copy import deepcopy

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

d = csg.floyd_warshall(c)






ans = 0

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

print(int(ans))

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

def main():
    H, W = map(int, readline().rstrip().split())
    C = [list(map(int, readline().rstrip().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])

    A = [tuple(map(int, readline().rstrip().split())) for _ in range(H)]
    cost = 0
    for h in range(H):
        for w in range(W):
            a = A[h][w]
            if 0 <= a <= 9:
                cost += C[a][1]
    
    print(cost)

if __name__ == '__main__':
    main()

Solution (Python):
from copy import deepcopy

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

d = deepcopy(c)

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 i in range(h):
    for j in range(w):
        if a[i][j] != -1:
            ans += d[a[i][j]][1]

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)

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


change=[list(map(int, input().split())) for i in range(10)]
test_case=[list(map(int, input().split())) for i in range(h)]
cost=[0]*10

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

def DEF(start,backed,weight,non_used):
    global cost,change
    
    if non_used==[]:
        return 0

    for item in non_used:
        if weight+change[backed][item]+change[item][1]<cost[start]:
            cost[start]=weight+change[backed][item]+change[item][1]
        if weight+change[backed][item]<cost[start]:
            non_used2=[]
            for t in non_used:
                if t!=item:
                    non_used2.append(t)

            DEF(start,item,weight+change[backed][item],non_used2)

for item in range(10):
    if item!=1:

        temp=[]
        for i in range(10):
            if item!=i and i!=1:
                temp.append(i)
        
        DEF(item,item,0,temp)

result=0
for item in test_case:
    for item2 in item:
        if item2!=1 and item2!=-1:
            result+=cost[item2]

print(result)

Solution (Python):
from copy import deepcopy
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= deepcopy(c)

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 i in range(H):
  for j in range(W):
    if A[i][j]==-1 or A[i][j]==1:
      pass
    else:
      ans += d[A[i][j]][1]
      
print(ans)

Solution (Python):


def warshall_floyd(n, d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
                
    return d
h, w = map(int, input().split())
c = [list(map(int, input().split())) for i in range(10)]
a = [list(map(int, input().split())) for i in range(h)]
c = warshall_floyd(10, c)
import collections
dic = collections.defaultdict(int)
for i in range(h):
    for j in range(w):
        dic[a[i][j]] += 1
ans = 0
for key in dic.keys():
    if key != -1:
        ans += c[key][1] * dic[key]
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)]
def warshall_floyd(n, 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
dic = {}
for i in range(h):
    for j in range(w):
        if a[i][j] not in dic:
            dic[a[i][j]] = 1
        else:
            dic[a[i][j]] += 1
          
c = warshall_floyd(10, d=c)          

ans = 0
for i in dic.keys():
    if i != -1 and i != 1:
        ans += c[i][1] * dic[i]
print(ans)

Solution (Python):

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

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

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

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

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

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



def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))




import heapq

def main():
	h,w=MI()
	
	G=[]
	for _ in range(10):
		c=LI()
		G.append(c)
	
	
	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 _ in range(h):
		row=LI()
		for val in row:
			if abs(val)!=1:
				ans+=G[val][1]
	print(ans)
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	

if __name__ == "__main__":
	main()

Solution (Python):
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



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



def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)


def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True



def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret



h, w = map(int, input().split())        
c = [list(map(int, input().split())) for i in range(10)]
cnt = [0 for i in range(10)]
for i in range(h):
    a = list(map(int, input().split()))
    for j in a:
        if j != -1:
            cnt[j] += 1
d = warshall_floyd(c, 10)
ans = 0
for i in range(10):
    ans += cnt[i] * c[i][1]
print(ans)

Solution (Python):
def dijkstra(start_node, num_nodes, cost_dict):
    import heapq

    initial_nodes = cost_dict[start_node]
    min_costs = {start_node : 0}
    available_nodes = initial_nodes
    done_nodes = set([start_node])
    heapq.heapify(available_nodes)
    
    
    while len(available_nodes) > 0:
        (min_cost, dest_node) = heapq.heappop(available_nodes)
        if(dest_node in done_nodes):
            continue
        min_costs[dest_node] = min_cost
        done_nodes.add(dest_node)
        
        for new_node in cost_dict[dest_node]:
            new_node_cost = new_node[0] + min_cost
            new_node_dest = new_node[1]
            if(new_node_dest in done_nodes):
                continue
            heapq.heappush(available_nodes, (new_node_cost, new_node_dest))
    return min_costs

def main():
    import copy
    H, W = map(int, input().split())
    cost_dict_org={i:[] for i in range(10)}
    for i in range(10):
        c_list = list(map(int, input().split()))
        for j in range(10):
            cost_dict_org[i].append((c_list[j], j))
    
    min_cost_dict = {}
    

    for i in range(10):
        cost_dict = copy.deepcopy(cost_dict_org)
        min_dict = dijkstra(i, 10, cost_dict)
        min_cost_dict[i]=min_dict
    
    A = []

    answer = 0
    for h in range(H):
        a_row = list(map(int, input().split()))
        for a in a_row:
            if(a == 1 or a == -1):
                continue
            else:
                answer += min_cost_dict[a][1]
    print(answer)


main()

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

INF = float("inf")


def warshall_floyd(n, d):
    for k in range(n):
        for i in range(n):
            d_ik = d[i][k]
            
            
            for j in range(n):
                if d[i][j] > d_ik + d[k][j]:
                    d[i][j] = d_ik + d[k][j]


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

    warshall_floyd(10, c)

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


if __name__ == "__main__":
    main()

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

INF = float("inf")


def warshall_floyd(n, d):
    for k in range(n):
        for i in range(n):
            d_ik = d[i][k]
            if d_ik == INF:
                continue
            for j in range(n):
                if d[i][j] > d_ik + d[k][j]:
                    d[i][j] = d_ik + d[k][j]


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

    warshall_floyd(10, c)

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


if __name__ == "__main__":
    main()

Solution (Python):
H,W=list(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])
res=0

for i in range(H):
    for j in range(W):
        a=A[i][j]
        if a>=0:
            res+=c[a][1]

print(res)

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

INF = float("inf")


def f(c, pos, unused, sum_c):
    if pos == 1:
        return sum_c
    ret = INF
    l = unused[:]
    l.remove(pos)
    for next_n in l:
        res = f(c, next_n, l, sum_c + c[pos][next_n])
        if res < ret:
            ret = res
    return ret


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

    c_min = [0] * 10
    for i in range(10):
        c_min[i] = f(c, i, list(range(10)), 0)

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


if __name__ == "__main__":
    main()

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

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

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

Solution (Python):
from collections import Counter

def main():
    h, w = map(int, input().split())
    c = [[int(i) for i in input().split()] for _ in range(10)]
    for k in range(10):
        for i in range(10):
            for j in range(10):
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])
    print(sum(c[k][1] * v for k, v in Counter(sum([[int(i) for i in input().split() if i != "-1"] for _ in range(h)], [])).items()))

if __name__ == '__main__':
    main()

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

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



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


count = 0
for i in range(H):
    for j in range(W):
        if As[i][j] >= 0:
            
            count += Cs[As[i][j]][1]

print(count)

Solution (Python):
import sys

sys.setrecursionlimit(1000000)


def z(changeable: [], cc: [], ans_set):
    for nums, limit_c in changeable:
        
        num = nums[-1]
        next_ls = []
        target = cc[num]
        limit = limit_c

        if target[1] < limit:
            limit = target[1]
            sub = target[1]
            for i in range(len(nums)-1):
                sub += cc[nums[i]][nums[i+1]]
            ans_set.add(sub)

        for i in range(10):
            if i in nums:
                continue
            x = target[i]
            if x < limit:
                nums_cp = nums[:]
                nums_cp.append(i)
                next_ls.append((nums_cp, limit - x))
        z(next_ls, cc, ans_set)


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

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

    
    to1dic = {}
    for i in range(10):
        if i == 1:
            continue
        target = cc[i]
        
        limit = target[1]
        changeables = []
        ans_set = {limit}
        for j in range(10):
            if j == i:
                continue
            x = target[j]
            if x < limit - 1:
                changeables.append(([i, j], limit - x))

        z(changeables, cc, ans_set)

        min_v = min(ans_set)

        to1dic.setdefault(i, min_v)

    total = 0
    for i in range(h):
        for j in range(w):
            num = wall[i][j]
            if num == -1 or num == 1:
                continue
            total += to1dic[num]
    
    print(total)


main()

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

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

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

print(ans)

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W = map(int, readline().split())
    C = [[int(i) for i in readline().split()] for _ in range(10)]
    A = [[int(i) for i in readline().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][k] + C[k][j], C[i][j])
    
    ans = 0
    for a in A:
        for i in a:
            if i != -1 and i != 1:
                ans += C[i][1]

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    H, W = map(int, input().split())
    c = []
    A = []
    for i in range(10):
        c.append(list(map(int, input().split())))
    for i in range(H):
        A.append(list(map(int, input().split())))
    
    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 or A[i][j] == 1):
                continue
            ans += c[A[i][j]][1]
    print(ans)    
main()

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

dist = [[float('inf')] * 10 for i in range(10)]
for i in range(10):
    c = list(map(int, input().split()))
    for j in range(10):
        dist[i][j] = c[j]


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

board = [list(map(int, input().split())) for i in range(n)]

cnt = 0
for row in board:
    for i in row:
        if (i == -1) or (i == 1):
            continue
        else:
            cnt += dist[i][1]
print(cnt)

Solution (Python):
from itertools import *
H,W=map(int,input().split())
c=[list(map(int,input().split())) for i in range(10+H)]
for k,i,j in product(list(range(10)),repeat=3):
    c[i][j]=min(c[i][j],c[i][k]+c[k][j])
print(sum(c[c[i+10][j]][1] if c[i+10][j]!=-1 else 0 for j in range(W) for i in range(H)))

Solution (Python):
import itertools
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,i,j in itertools.product(list(range(10)),repeat=3):
    c[i][j]=min(c[i][j],c[i][k]+c[k][j])
res=sum(c[A[i][j]][1] if A[i][j]!=-1 else 0 for j in range(W) for i in range(H))
print(res)