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
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
c = [LIST() for _ in range(10)]
A = [LIST() for _ in range(H)]


from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

graph = csr_matrix(c) 
c = floyd_warshall(graph, directed=True) 

	




import numpy as np

def distance(p1, p2):
	p1 = np.array(p1)
	p2 = np.array(p2) 
	return np.linalg.norm(p1-p2)
	

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

print(int(ans))

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

H, W = MAP()
c = [LIST() for _ in range(10)]
A = [LIST() for _ in range(H)]


from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

graph = csr_matrix(c) 
c = floyd_warshall(graph, directed=True) 

	




import numpy as np

def distance(p1, p2):
	p1 = np.array(p1)
	p2 = np.array(p2) 
	return np.linalg.norm(p1-p2)
	

ans = 0
for i in range(H):
	for x in A[i]:
		if x == 1 or x == -1:
			continue
		else:
			ans += c[x][1]

print(int(ans))

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

H, W = MAP()
c = [LIST() for _ in range(10)]
A = [LIST() for _ in range(H)]


from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

graph = csr_matrix(c) 
c = floyd_warshall(graph, directed=True) 





ans = 0
for i in range(H):
	for x in A[i]:
		if x == 1 or x == -1:
			continue
		else:
			ans += c[x][1]

print(int(ans))

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

H, W = MAP()
c = [LIST() for _ in range(10)]
A = [LIST() for _ in range(H)]

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




ans = 0
for i in range(H):
	for x in A[i]:
		if x == 1 or x == -1:
			continue
		else:
			ans += c[x][1]

print(ans)

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

ndict = {i:0 for i in range(10)}
for i in range(H):
  for j in map(int, input().split()):
    if j == -1:
      continue
    ndict[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])

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

Solution (Python):
h,w=map(int,input().split())
d=[list(map(int,input().split())) for _ in range(10)]
e=[list(map(int,input().split())) for _ in range(h)]
def warshall_floyd(d,n):
    
    for k in range(n+1):
        for i in range(n+1):
            for j in range(n+1):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
d=warshall_floyd(d,9)
ans=0
for i in range(h):
    for j in range(w):
        if e[i][j]>=0:
            ans+=d[e[i][j]][1]
print(ans)

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

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

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

res = 0
for a in A:
  for e in a:
    if e != -1 and e != 1:
      res += c[e][1]

print(res)

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,list(input().split()))) for _ in range(10)]
a=[list(map(int,list(input().split()))) for _ in range(h)]
e=[x[1] for x in warshall_floyd(10,c)]

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

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

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

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

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



for k in range(10):
    for i in range(10):
        for j in range(10):
            C_mat[i][j] = min(C_mat[i][j], C_mat[i][k]+ C_mat[k][j])
            
            
            
            
ans = 0
for i in range(H):
    for j in range(W):
        if A_mat[i][j] != -1:
            ans += C_mat[A_mat[i][j]][1]
            
print(ans)

Solution (Python):
import sys
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    H, W = map(int, readline().split())
    L = list(list(map(int, readline().split())) for _ in range(10))
    path = dijkstra(csr_matrix(L))
    ans = 0
    for i in range(H):
        A = list(map(int, readline().split()))
        for j in range(W):
            a = A[j]
            if a!=-1:
                ans += path[a][1]
    print(int(ans))

if __name__ == '__main__':
    main()

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

memo = [float("INF")]*(10)
memo[1] = 0
flag = True
while flag:
    flag = False
    for i in range(10):
        for j in range(10):
            if memo[i]+costMap[j][i] < memo[j]:
                memo[j] = memo[i]+costMap[j][i]
                flag = True
ans = 0
for i in range(H):
    for j in range(W):
        a = wall[i][j]
        if a != -1:
            ans += memo[a]
print(ans)

Solution (Python):




import math
import sys
import bisect
import heapq  
from collections import deque

inf = 10 ** 15
mod = 10 ** 9 + 7

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

print(ans)

Solution (Python):
N,M=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(10)]
s=[list(map(int,input().split())) for i in range(N)]
from scipy.sparse.csgraph import floyd_warshall
l=floyd_warshall(l)
ans=0
for i in s:
   for j in i:
      ans+=0 if j == -1 else l[j][1]
print(int(ans))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

    dp = [[INF] * 10 for _ in range(10)]
    for i in range(10):
        for j in range(10):
            dp[i][j] = C[i][j]

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

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

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
h,w=map(int,input().split())
C=[]
for index1 in range(10):
    C.append(list(map(int,input().split())))
A=[]
for index2 in range(h):
    A.append(list(map(int,input().split())))

def warshall_floyd(G):

    
    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

D=warshall_floyd(C)
magic=[0]*10
for index3 in range(10):
    if index3!=1:
        magic[index3]=D[index3][1]

ans=0
for index4 in range(h):
    for index5 in range(w):
        if A[index4][index5]>-1:
            ans+=magic[A[index4][index5]]

print(ans)

Solution (Python):
def shortpath(C):
    
    update = True
    while update:
        update = False
        for i in range(10):
            for j in range(10):
                for k in range(10):
                    if C[i][j] > C[i][k] + C[k][j]:
                        C[i][j] = C[i][k] + C[k][j]
                        update = True
    return C

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

    C = shortpath(C)
    ans = 0
    for i in range(H):
        for j in range(W):
            if abs(A[i][j]) != 1:
                ans += C[A[i][j]][1]

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import collections

class WarshallFloyd():
    def __init__(self,N):  
        self.N = N
        self.d = [[float('inf')]*N for i in range(N)]  
    def add(self,u,v,c,directed = False):
        if directed is False:  
            self.d[u][v] = c
            self.d[v][u] = c
        else:  
            self.d[u][v] = c
    def WarshallFloyd_search(self):
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(self.d[i][j],self.d[i][k] + self.d[k][j])
        for i in range(self.N):
            self.d[i][i] = 0
        return self.d

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

G = WarshallFloyd(10)

for i in range(10):
    for j in range(10):
        G.add(i,j,A[i][j],directed=True)

d = G.WarshallFloyd_search()

C = []
for i in range(10):
    C.append(d[i][1])

D = [0]*11
for i in range(H):
    for j in range(W):
        if B[i][j] == -1:
            D[10] += 1
        else:
            D[B[i][j]] += 1

ans = 0
for i in range(10):
    ans += C[i]*D[i]

print(ans)

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

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


n = 10
d = [[float("inf")]*n for i in range(n)] 

for x in range(n):
    for y in range(n):
        d[x][y] = c[x][y]
        d[y][x] = c[y][x]
for i in range(n):
    d[i][i] = 0 
cost = warshall_floyd(d)
ans = 0
for h in range(H):
    for w in range(W):
        if grid[h][w] != -1:
            ans += cost[grid[h][w]][1]
print(ans)

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

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

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


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

for i in range(10):
 d[i] = list(map(int,input().split()))
ct=[0]*11
for i in range(H):
  lst=list(map(int,input().split()))
  for j in range(W):
   ct[lst[j]+1]+=1

A=warshall_floyd(d,10)
ans=0
for i in range(10):
 ans+=ct[(i+1)]*A[i][1]
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):
from scipy.sparse.csgraph import floyd_warshall
from itertools import chain

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

d = floyd_warshall(C)

ans = sum(d[a][1] for a in chain(*A) if a != -1)

print(int(ans))

Solution (Python):
from collections import Counter
h,w = map(int,input().split())
c = [list(map(int,input().split())) for _ in range(10)]
a = []
for i in range(h):
    a += list(map(int,input().split()))
C = Counter(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])
ans = 0
for i,n in C.items():
    if i != -1:
        ans += c[i][1]*n
print(ans)

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

for stop in range(10):
    for start in range(10):
        for end in range(10):
            cost_mat[start][end] = min(cost_mat[start][end], cost_mat[start][stop] + cost_mat[stop][end])
cost = 0
for h in range(H):
    in_ls = list(map(int, input().split()))
    for num in in_ls:
        if not num == -1:
            cost += cost_mat[num][1]
print(cost)

Solution (Python):
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


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


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):
                if C[i][j] > C[i][k] + C[k][j]:
                    C[i][j] = C[i][k] + C[k][j]
                    
    ans = 0
    for row in A:
        for n in row:
            if n != -1:
                ans += C[n][1]
    
    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


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


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):
                if C[i][j] > C[i][k] + C[k][j]:
                    C[i][j] = C[i][k] + C[k][j]
                    
    ans = 0
    for row in A:
        for n in row:
            if n != -1:
                ans += C[n][1]
    
    print(ans)
    return


if __name__ == '__main__':
    main()

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

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

result = 0
for _ in range(H):
    for i in map(int, input().split()):
        if i == -1:
            continue
        result += c[i][1]
print(int(result))

Solution (Python):
h,w = map(int,input().split())
ma = [list(map(int,input().split())) for _ in range(10)]
for i in range(10):
    for j in range(10):
        for k in range(10):
            ma[j][k] = min(ma[j][k], ma[j][i]+ma[i][k])
li = [list(map(int,input().split())) for _ in range(h)]
ans = 0
for each_li in li:
    for l in each_li:
        if l!=-1:
            ans += ma[l][1]
print(ans)

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

Solution (Python):

import numpy as np
from scipy.sparse.csgraph import floyd_warshall, csgraph_from_dense
from itertools import*
from collections import*

h, w = map(int, input().split())
G = [list(map(int, input().split())) for _ in [0]*10]

m = floyd_warshall(csgraph_from_dense(G))

d = list(chain.from_iterable(list(map(int, input().split())) for _ in [0]*h))
C = Counter(d)
s = 0
for i in range(10):
    s += m[i][1] * C.get(i, 0)
print(int(s))

Solution (Python):

from collections import defaultdict, deque
from copy import copy

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

d = defaultdict(lambda: float("inf"))
d["1_1"] = 0
nums = [i for i in range(10) if i != 1]

q = deque([[[1], 0]])

while q:
    tmp = q.pop()
    num, cost = tmp[0], tmp[1]
    if len(num) > 1:
        key = str(num[-1]) + "_1"
        d[key] = min(d[key], cost)
    if len(num) < 10:
        for n in nums:
            num_tmp = copy(num)
            if n not in set(num_tmp):
                num_tmp.append(n)
                q.append([num_tmp, cost + c[n][num_tmp[-2]]])

ans = 0
for i in range(H):
    for j in range(W):
        tmp = grid[i - 1][j - 1] 
        if tmp >= 0:
            ans += d[str(tmp) + "_1"]
print(ans)

Solution (Python):

import copy

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

d = dict()
nums = [i for i in range(10) if i != 1]
d["-1_1"] = 0

q = [[[1], 0]]

while q:
    tmp = q.pop()
    num, cost = tmp[0], tmp[1]
    key = str(num[-1]) + "_1"
    if d.get(key):
        d[key] = min(d[key], cost)
    else:
        d[key] = cost
    if len(num) < 10:
        for n in nums:
            num_tmp = copy.copy(num)
            if n not in set(num_tmp):
                num_tmp.append(n)
                q.append([num_tmp, cost + c[num_tmp[-1]][num_tmp[-2]]])

ans = 0
for i in range(H):
    for j in range(W):
        tmp = grid[i - 1][j - 1] 
        ans += d[str(tmp) + "_1"]
print(ans)

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

def abc079_d():
    inp = iter(map(int, read().split()))
    H, W = next(inp), next(inp)
    adj_mtx = [[next(inp) for _ in range(10)] for _ in range(10)]
    grid = [[next(inp) for _ in range(W)] for _ in range(H)]

    def floyd_warshall(W):
        ''' ワーシャルフロイド法、全頂点間の最短距離 '''
        n = len(W)  
        
        for k in range(n):
            for u in range(n):
                for v in range(n):
                    W[u][v] = min(W[u][v], W[u][k] + W[k][v])
        return W

    min_dist = floyd_warshall(adj_mtx)

    
    ans = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == -1 or grid[i][j] == 1:
                continue
            ans += min_dist[grid[i][j]][1]
    print(ans)

abc079_d()

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

def abc079_d():
    inp = iter(map(int, read().split()))
    H, W = next(inp), next(inp)
    adj_mtx = [[next(inp) for _ in range(10)] for _ in range(10)]
    grid = [[next(inp) for _ in range(W)] for _ in range(H)]

    import heapq
    def dijkstra(start, W):
        ''' スタート地点から到達可能なすべての頂点への最短距離を返す
            Pythonで学ぶアルゴリズムとデータ構造 P.111 一部変更
        '''
        
        inf = 10**9
        distance_list = [inf] * len(W)
        
        distance_list[start] = 0
        
        done_list = []
        
        wait_heap = []
        for i, d in enumerate(distance_list):
            
            heapq.heappush(wait_heap, (d, i))
        
        while wait_heap:
            p = heapq.heappop(wait_heap)
            i = p[1]
            if i in done_list:
                continue
            
            done_list.append(i)
            
            for j, x in enumerate(W[i]):
                if x > -1 and j not in done_list:
                    
                    d = min(distance_list[j], distance_list[i] + x)
                    distance_list[j] = d
                    
                    heapq.heappush(wait_heap, (d, j))
        return distance_list

    
    dist_to_1 = [None] * 10
    for i in range(10):
        dist_to_1[i] = dijkstra(i, adj_mtx)[1]

    
    ans = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == -1 or grid[i][j] == 1:
                continue
            ans += dist_to_1[grid[i][j]]
    print(ans)

abc079_d()

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

trans_map = warshall_floyd(C)
ans = 0
for _ in range(h):
    A = list(map(int,input().split()))
    for a in A:
        if a==-1:
            continue
        else:
            ans += trans_map[a][1]
print(ans)

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

c2 = [[0 for _ in range(10)]for _ in range(10)]

for i in range(10):
    for j in range(10):
        c2[i][j] = c[i][j]+c[j][1]

d = []
for i in range(10):
    d.append(min(c2[i]))

for _ in range(10):
    c2 = [[0 for _ in range(10)]for _ in range(10)]
    for i in range(10):
        for j in range(10):
            c2[i][j] = c[i][j]+d[j]
    d = []
    for i in range(10):
        d.append(min(c2[i]))
su = 0
for i in range(H):
    for j in range(W):
        if A[i][j] >=0:
            su+=d[A[i][j]]
print(su)

Solution (Python):
import numpy as np
import scipy.sparse as sps
import sys,math

h,w = map(int,input().split())
c = np.array([list(map(int,input().split()))for i in range(10)])
wf = sps.csgraph.floyd_warshall(c,directed=1).astype(int)

a = np.array([list(map(int,input().split()))for i in range(h)])

ans = 0
for arr in a:
    for num in arr:
        if num == -1: continue
        else: ans += wf[num][1]
print(ans)

Solution (Python):
from collections import Counter

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

cost = [10**5]*10
cost[1] = 0
temp = [['1', 0]]

while temp:
    p = temp.pop()
    if len(p[0]) < 10:
        for s in '0123456789':
            if s in p[0]:continue
            else:
                nxt = p[1] + c[int(s)][int(p[0][-1])]
                if cost[int(s)] > nxt:
                    temp.append([p[0] + s, nxt])
                    cost[int(s)] = nxt
        
d = Counter(a)
ans = 0
for i in range(10):
    ans += d[i]*cost[i]
print(ans)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def warshall_floyd(d):
    V = len(d)
    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

def resolve():
    H, W = LI()
    c = [LI() for _ in range(10)]
    A = [LI() for _ in range(H)]

    min_cost = warshall_floyd(c)
    
    
    ans = 0
    for i in A:
        for j in i:
            if 0<=j<=9:
                ans += min_cost[j][1]
    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import Counter
import heapq

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

Power_map = [0]*10

for i in range(10):
    Q = []
    if i == 1:
        continue
    if Power[i][1] == min(Power[i]):
        Power_map[i] = Power[i][1]
    else:
        to1 = Power[i][1]
        heapq.heappush(Q, (to1, 1))
        for j in range(10):
            if (i == j) or j == 1:
                continue
            elif to1 > Power[i][j]:
                heapq.heappush(Q, (Power[i][j], j))
        while len(Q) > 0:
            Costsum, now = heapq.heappop(Q)
            if now == 1:
                Power_map[i] = Costsum
                break
            for k in range(10):
                if now == k:
                    continue
                elif Costsum + Power[now][k] < to1:
                    heapq.heappush(Q, (Costsum+Power[now][k], k))

Wall = []
for _ in range(H):
    wall = list(map(int, input().split()))
    for __ in range(W):
        if wall[__] >= 0:
            Wall.append(wall[__])
WallC = Counter(Wall)

ans = 0
for i in range(10):
    ans += WallC[i] * Power_map[i]

print(ans)