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

from scipy.sparse.csgraph import floyd_warshall

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

H, W = MAP()
G = build_grid(10, 10, 0, int)
grid = build_grid(H, W, 0, int)


wf = floyd_warshall(G)

ans = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] != -1:
            a = grid[i][j]
            
            ans += int(wf[a,1])
print(ans)

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

I = np.array(sys.stdin.read().split(), dtype=np.int64)
h, w = I[:2]
c = I[2:102].reshape(10, 10).T
a = I[102:].reshape(h, w)
                                                              
def main():
    cost = dijkstra(csr_matrix(c), directed=True, indices=1).astype(np.int64)

    return np.sum(cost[a[a != -1]])

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys
import numpy as np 
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

I = np.array(sys.stdin.read().split(), dtype=np.int64)
h, w = I[:2]
c = I[2:102].reshape(10, 10)
a = I[102:].reshape(h, w)
                                                              
def main():
    cost = floyd_warshall(csr_matrix(c), directed=True).astype(np.int64)
    
    res = cost[a[a != -1], 1]
    return np.sum(res)

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	H, W = MAP()
	TABLE = [MAP() for _ in range(10)]
	A = [MAP() for _ in range(H)]

	to_one = [t[1] for t in TABLE]
	queue = deque([i for i in range(10)])
	
	while queue:
		
		mi = queue.popleft()
		for i, t in enumerate(TABLE):
			if i == mi: continue
			if t[mi]+to_one[mi] < to_one[i]:
				to_one[i] = t[mi]+to_one[mi]
				queue.append(i)
	
	
	
	ans = 0
	for row in A:
		for a in row:
			if a != -1: ans += to_one[a]
	
	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=[]
ans=0
for i in range(h):
	a.append(list(map(int,input().split())))
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])
for j in range(h):
	for k in range(w):
		if a[j][k]==-1:
			continue
		else:
			ans+=c[a[j][k]][1]
print(ans)

Solution (Python):


h,w=map(int,input().split())
li=[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):
            li[i][j] = min(li[i][j], li[i][k] + li[k][j])

ans=0

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

Solution (Python):
import sys
input=sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import shortest_path


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

graph = np.zeros((10,10))
for i in range(10):
    for j in range(10):
        graph[i,j] = c[i][j]
dist = shortest_path(graph,directed=True).astype(int)


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

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




seq=(0,1,2,3,4,5,6,7,8,9)
mi=[float("inf")]*10 

import itertools
for ptn in itertools.permutations(seq):
  num=ptn[0] 
  en=0 
  for i in range(9):
    if ptn[i]==1:
      break
    else:
      en+=li[ptn[i]][ptn[i+1]]
  mi[num]=min(mi[num], en)

ans=0

for i in a:
  for j in i:
    if j!=-1:
      ans+=mi[j]
print(ans)

Solution (Python):
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:
      ans += c[a[i][j]][1]
print(ans)

Solution (Python):
h,w = map(int, input().split(' '))
tbl = [list(map(int, input().split(' '))) for i in range(10)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            tbl[i][j] = min(tbl[i][j], tbl[i][k]+tbl[k][j])
wall = [list(map(int, input().split(' '))) for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        num = wall[i][j]
        if num == -1:
            continue
        else:
            ans += tbl[num][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 h 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 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 = [list(map(int, input().split())) for i in range(10)]
A = [list(map(int, input().split())) for h 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 h in range(H):
  for w in range(W):
    if A[h][w] >= 0:
      ans += c[A[h][w]][1]
print(ans)

Solution (Python):
'''
　 ∧_,,∧    究極奥義「WAがACになーれ！！」
　（`・ω・)つ━☆・*。
　⊂　　 ノ 　　　・゜+.
　 し’´Ｊ　　*・ 
'''
import sys
input = sys.stdin.readline
h,w=map(int,input().split())
d=[list(map(int,input().split())) for i in range(10)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
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+=d[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) ] 

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
B=warshall_floyd(C)
  
ans=0
for i in range(H):
  for j in range(W):
    if A[i][j]!=-1:
      ans+=B[ A[i][j] ][1]
print(ans)

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

H, W = map(int, input().split())
path = shortest_path(np.array(tuple(tuple(map(int, input().split())) for _ in range(10))))
A = np.array(tuple(tuple(map(int, input().split())) for _ in range(H))).flatten()

print(int(sum(path[n][1] for n in A if n not in [-1, 1])))

Solution (Python):

def warshal_floyd(weights,N):
    d=weights
    for i in range(N):
        d[i][i]=0
    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

if __name__ == '__main__':
    H,W=list(map(int,input().split()))
    weights=[[None for i in range(10)] for j in range(10)]
    for i in range(10):
        Cs = list(map(int, input().split()))
        for j in range(10):
            weights[i][j]=Cs[j]
    wall=[]

    for i in range(H):
        temp=list(map(int,input().split()))
        wall.append(temp)

    paths=warshal_floyd(weights,10)
    cost=0

    for row in wall:
        for a in row:
            if a==-1:
                continue
            else:
                cost+=paths[a][1]
    print(cost)

Solution (Python):
def dijkstra(v, G):
    import heapq

    ret = [10 ** 10] * len(G)
    ret[v] = 0
    q = [(ret[i], i) for i in range(len(G))]
    heapq.heapify(q)

    while len(q):
        tmpr, u = heapq.heappop(q)
        if tmpr == ret[u]:
            for w, l in G[u]:
                if ret[w] > ret[u] + l:
                    ret[w] = ret[u] + l
                    heapq.heappush(q, (ret[w], w))
    return ret


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

LUT = [dijkstra(i, G)[1] for i in range(10)]

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

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

edges = [[] for i in range(10)]

for _from in range(10):
    line = list(map(int, input().split()))
    for to in range(10):
        if _from == to:
            continue
        cost = line[to]
        edges[_from].append([to, cost])

cost_to_1 = [10**5] * 10
cost_to_1[1] = 0

for num in range(10):
    if num == 1:
        continue
    min_cost_to = [10**5] * 10
    min_cost_to[num] = 0
    todo = []
    for to, cost in edges[num]:
        if to == num:
            continue
        min_cost_to[to] = cost
        todo.append(to)

    while todo:
        now = todo.pop()
        cost = min_cost_to[now]
        for to, add_cost in edges[now]:
            if to == now:
                continue
            if cost + add_cost < min_cost_to[to]:
                min_cost_to[to] = cost + add_cost
                todo.append(to)
            else:
                continue

    cost_to_1[num] = min_cost_to[1]

ans = 0
for i in range(h):
    line = list(map(int, input().split()))
    for num in line:
        if num == -1 or num == 1:
            continue
        ans += cost_to_1[num]

print(ans)

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

for i in range(10):
    dist[i]=A[i][1]

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

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

Solution (Python):
h,w = map(int,input().split())
ans = 0
c = [list(map(int,input().split()))for i in range(10)]
a = [list(map(int,input().split()))for _ 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])
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):
a,b = list(map(int,input().split()))
mat = []
for i in range(10):
  mat.append(list(map(int,input().split())))

xs = []
for i in range(a):
  xs += list(map(int,input().split()))

import heapq  
d_ans = [0]*10

for i in range(10):
  d = [3000 *20] * 10
  d[i] = 0
  h = []
  heapq.heappush(h,(d[i],i))
  
  while not len(h) == 0:
    (di, v) = heapq.heappop(h)
    if v == 1:
      break
    for j in range(10):
      
      if d[j] > d[v] + mat[v][j]:
        d[j] = d[v] + mat[v][j]
        heapq.heappush(h,(d[j],j))
  
  d_ans[i] = d[1]

ans = 0
for x in xs:
  if x != -1:
    ans += d_ans[x]
print(ans)

Solution (Python):
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    inf = 10 ** 13
    h, w = list(map(int, input().rstrip('\n').split()))
    wn = 10
    wl = [[inf] * wn for _ in range(wn)]

    for i in range(wn):
        twl = list(map(int, input().rstrip('\n').split()))
        for j in range(wn):
            wl[i][j] = twl[j]

    for i in range(wn):
        for j in range(wn):
            for k in range(wn):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])

    cost = 0
    for i in range(h):
        hw = list(map(int, input().rstrip('\n').split()))
        for j in range(w):
            if hw[j] != -1:
                cost += wl[hw[j]][1]
    print(cost)


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 j in range(10):
        for i in range(10):
            C[i][j] = min(C[i][j], C[i][k]+C[k][j])

powerto1 = {idx: C[idx][1] for idx in range(10)}

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

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

powerto1 = {idx: C[idx][1] for idx in range(10)}

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

Solution (Python):
dp=[[0 for j in range(10)] for i in range(10)]
import numpy as np

h,w=map(int,input().split())
dp=np.array(dp)
for i in range(10):
    s=list(map(int,input().split()))
    for j in range(10):
        dp[i][j]=s[j]

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

Solution (Python):
dp=[[0 for j in range(10)] for i in range(10)]

h,w=map(int,input().split())
for i in range(10):
    s=list(map(int,input().split()))
    for j in range(10):
        dp[i][j]=s[j]

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

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)]
ans = 0

manacost = [0]*11
for i in range(10):
    if i == 1:
        continue
    manacost[i] = c[i][1]
    stack = []
    for j, m in enumerate(c[i]):
        if j == 1 or i == j:
            continue
        else:
            if manacost[i] > m:
                stack.append((j, m, 0))
    while len(stack):
        j, m, t = stack.pop()
        for k, n in enumerate(c[j]):
            if j == k:
                continue
            elif k == 1:
                manacost[i] = min(manacost[i], m+n)
            else:
                if manacost[i] > m+n and t < 9:
                    stack.append((k, n+m, t+1))
for ary in A:
    for a in ary:
        ans += manacost[a]
print(ans)

Solution (Python):
dp=[[0 for j in range(10)] for i in range(10)]

h,w=map(int,input().split())
for i in range(10):
    s=list(map(int,input().split()))
    for j in range(10):
        dp[i][j]=s[j]

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

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


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

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
mod = 10**9+7


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

from scipy.sparse.csgraph import floyd_warshall
D = floyd_warshall(C)

cnt = [0]*10
for i in range(H):
    for j in range(W):
        if A[i][j] != -1:
            cnt[A[i][j]] += 1

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

print(int(ans))

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

H, W = [int(x) for x in input().strip().split()]
C = [0 for _ in range(10)]
for i in range(10):
    C[i] = [int(x) for x in input().strip().split()]

isChanged = True
while isChanged:
    isChanged = False
    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]
                    isChanged = True
    if not isChanged:
        break

ans = 0
for h in range(H):
    W = [int(x) for x in input().strip().split()]
    for w in W:
        if w == -1:
            continue
        ans += C[w][1]

print(ans)

Solution (Python):
import sys
import heapq
from collections import Counter
h, w = [int(i) for i in sys.stdin.readline().split()]
c_ls = []
A = dict()
for i in range(10):
    c_ls.append([int(i) for i in sys.stdin.readline().split()])
c_ls_true = {i : [0 for j in range(10)] for i in range(10)}
for i in range(10):
    for j in range(10):
        c_ls_true[i][j] = c_ls[j][i]

shortest_path = {-1 : 0}
que = [(0, 1)]
already = set()
while len(que) > 0:
    cur_cost, cur = heapq.heappop(que)
    if cur in already:
        continue
    already.add(cur)
    shortest_path[cur] = cur_cost
    for _next, cost in enumerate(c_ls_true[cur]):
        if _next not in already:
            heapq.heappush(que, (cur_cost + cost, _next))
    if len(already) == 10:
        break
ct = Counter()
for i in range(h):
    inp = [int(i) for i in sys.stdin.readline().split()]
    A[i] = inp
    ct.update(inp)
res = 0
for k, v in ct.items():
    res += shortest_path[k] * v
print(res)

Solution (Python):
from itertools import permutations as per
h,w = map(int,input().split())
c = [list(map(int,input().split())) for i in range(10)]
ans = 0
mc = [0]*10
for i in range(10):
  mc[i] = c[i][1]
for i in range(1,10):
  for j in per([0,2,3,4,5,6,7,8,9],i):
    cur = 0
    for k in range(1,i):
      cur += c[j[k-1]][j[k]]
    cur += c[j[i-1]][1]
    mc[j[0]] = min(mc[j[0]],cur)
for i in range(h):
  a = list(map(int,input().split()))
  for j in a:
    if j != -1:
      ans += mc[j]
print(ans)

Solution (Python):
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
h, w = map(int, input().split())
c = [ list(map(int, input().split())) for _ in range(10) ]
csr = csr_matrix(c)
A = dijkstra(csr)
Q = [0]*10
for i in range(10):
  Q[i] = int(A[i][1])
ans = 0
for _ in range(h):
  for i in map(int, input().split()):
    if not i==-1:
      ans += Q[i]
print(ans)

Solution (Python):

import sys

def warshall_floyd(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 

def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):
    min_cost = warshall_floyd(c,10)
    answer = 0

    for h in range(H):
        for w in range(W):
            if A[h][w] == -1:
                continue

            answer += min_cost[A[h][w]][1]
    print(answer)
    return


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):
h,w = map(int,input().split())

from collections import defaultdict
cost = [[float("inf") for i in range(10)] for j in range(10)]
for i in range(10):
    cl = list(map(int,input().split()))
    for j in range(10):
        cost[i][j] = cl[j]


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

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

print(ans)

Solution (Python):
def main():
    H, W = map(int, input().split())
    C = list(list(map(int, input().split())) for _ in range(10))
    A = list(list(map(int, input().split())) for _ in range(H))
    for k in range(10):
        for i in range(10):
            for j in range(10):
                C[i][j] = min(C[i][j], C[i][k] + C[k][j])

    ans = 0
    for h in range(H):
        for w in range(W):
            if 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)]
P = [c[:] for c in C]

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

ans = 0
for _ in range(H):
    for a in map(int, input().split()):
        if a!=-1:
            ans += P[a][1]
    
print(ans)

Solution (Python):


from scipy.sparse.csgraph import floyd_warshall

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

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

Solution (Python):
H, W = map(int, input().split())
X = [[int(a) for a in input().split()] for _ in range(10)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            X[i][j] = min(X[i][j], X[i][k] + X[k][j])
print(sum([sum([0 if a == "-1" else X[int(a)][1] for a in input().split()]) for _ in range(H)]))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

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

dist = [[INF]*10 for _ in range(10)]
for i in range(10):
    for j in range(10):
        dist[i][j] = c[i][j]

graph = csr_matrix(dist)
dist_mat = floyd_warshall(graph, directed=True)

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

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

v=[[l[j][1] if j>=0 else 0 for j in i] for i in o]
print(sum(map(sum,v)))

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

def warshallFloyd(dp):
    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
warshallFloyd(dp)
for i in range(H):
    for j in range(W):
        a = A[i][j]
        if a == -1:
            continue
        else:
            ans += dp[a][1]
print(ans)

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


dis=[l[i][1] for i in range(10)] 

for i in range(9):
    dis=[min(dis[v],min([dis[u]+l[v][u] for u in range(10)])) for v in range(10)]
    

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

ans=sum([A.count(i)*dis[i] for i in range(10)])
print(ans)

Solution (Python):
h,w=map(int,input().split())
l=[]
for i in range(10):
  l.append(list(map(int,input().split())))
way=[]
for i in range(h):
  way.append(list(map(int,input().split())))
from collections import deque
q=deque([[0,0]])
for k in range(10):
  for j in range(10):
    for i in range(10):
      l[i][j]=min(l[i][j],l[i][k]+l[k][j])
cost=0
d=[[-1 for i in range(w)] for j in range(h)]
if way[0][0]!=-1:
  cost+=l[way[0][0]][1]
d[0][0]=1
move=[[0,1],[0,-1],[-1,0],[1,0]]
while q:
  m=q.popleft()
  for i in move:
    x=m[0]+i[0]
    y=m[1]+i[1]
    if x<0 or y<0 or x>=h or y>=w:
      pass
    elif d[x][y]==1:
      pass
    else:
      d[x][y]=1
      if way[x][y]!=-1:
        cost+=l[way[x][y]][1]
      way[x][y]=1
      q.append([x,y])
print(cost)

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(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 = [[float("inf") for i in range(10)] for i in range(10)] 

for i in range(10):
  for j in range(10):
    d[i][j] = C[i][j]



cost = warshall_floyd(d)

num = [0] * 10
for i in range(H):
  for j in range(W):
    if A[i][j] != -1:
      kazu = A[i][j]
      num[kazu] += 1

ans = 0
for i in range(10):
  ans += num[i] * cost[i][1]

print(ans)

Solution (Python):
H,W = (int(i) for i in input().split())

C = []

for i in range(10):
  C.append([int(j) for j in input().split()])

for s in range(10):
  for i in range(10):
    for j in range(10):
      new_costs = []
      for k in range(10):
        new_costs.append(C[i][k] + C[k][j])

      C[i][j] = min(min(new_costs),C[i][j])

A_dict = {}
for i in range(H):
  A = [int(i) for i in input().split()]
  for a in A:
    A_dict[a] = A_dict.get(a,0)+1

ans = 0
for A in A_dict.keys():
  if A != -1 and A != 1:
    ans += C[A][1]*A_dict[A]

print(ans)

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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


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

a = [list(map(int, input().split())) for _ in range(h)]
cou = [0]*10
for i in a:
    for j in range(10):
        cou[j] += i.count(j)
ans = 0
for i in range(10):
    ans += cou[i]*d[i][1]

    
print(ans)