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

"""
@author: H_Hoshigi
解説PDFを読んで書き直した。
ワーシャル-フロイド法を用いる。
"""

def warshall_floyd(c_lsit_list):
    for i in range(10):
        for j in range(10):
            for k in range(10):
                c_lsit_list[j][k] = min(
                    c_lsit_list[j][i] + c_lsit_list[i][k],
                    c_lsit_list[j][k]
                )
    min_c_list = [c_lsit_list[i][1] for i in range(10)]
    return min_c_list

def main():
    H, W = map(int, input().split())
    c_lsit_list = [list(map(int, input().split())) for i in range(10)]
    A_lsit_list = [list(map(int, input().split())) for i in range(H)]

    A_bucket = [0]*10
    for A_list in A_lsit_list:
        for A in A_list:
            if A >= 0:
                A_bucket[A] += 1

    min_c_list = warshall_floyd(c_lsit_list)

    print(sum([A_bucket[i]*min_c_list[i] for i in range(10)]))
    return

if __name__ == "__main__":
    main()

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


def bellman_ford(s):
	d = [float('inf')]*10 
	d[s] = 0 
	for i in range(10):
		update = False 
		for x, y, z in g:
			if d[y] > d[x] + z:
				d[y] = d[x] + z
				update = True
		if not update:
 			break
		
		if i == 9:
			return -1
	return d

g = []
for i in range(10):
	for j in range(10):
		x,y,z = j,i,c[i][j]
		g.append([x,y,z])

MINCOST = bellman_ford(1)

sum = 0
for j in range(h):
	for i in range(0,10):
		sum += MINCOST[i]*collections.Counter(a[j])[i]
print(sum)

Solution (Python):
H, W = map(int, input().split())
C = []
wall = []

for _ in range(10):
  C.append(list(map(int, input().split())))

for _ in range(H):
  wall += 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 x in wall:
  if x == -1:
    continue
  else:
    ans += C[x][1]

print(ans)

Solution (Python):
import heapq

H, W = map(int, input().split())
graph = []
wall = []

for _ in range(10):
  graph.append(list(map(int, input().split())))

for _ in range(H):
  wall += list(map(int, input().split()))

def dijkstra(s):
  INF = 10**5
  hq = [(0, s)]
  heapq.heapify(hq)
  cost = [INF] * 10
  cost[s] = 0
  while hq:
    c, v = heapq.heappop(hq)
    if c > cost[v]:
      continue
    for u, d in enumerate(graph[v]):
      tmp = d + cost[v]
      if tmp < cost[u]:
        cost[u] = tmp
        heapq.heappush(hq, (tmp, u))
  return cost[1]

mincost = [0]*10
for i in range(10):
  mincost[i] = dijkstra(i)

ans = 0
for x in wall:
  if x == -1 or x == 1:
    continue
  else:
    ans += mincost[x]

print(ans)

Solution (Python):
H, W = map(int, input().split())
dist = [list(map(int, input().split())) for _ in range(10)]
for i in range(10):
    for j in range(10):
        for k in range(10):
            dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])
ans = 0
for _ in range(H):
    for i in list(map(int, input().split())):
        if i == 1 or i == -1:
            continue
        ans += dist[i][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)]
dp = [float("INF")]*(10)
dp[1] = 0
cnt = 0
while cnt <= 10:
    cnt += 1
    for i in range(10):
        for j in range(10):
            dp[j] = min(dp[j],dp[i]+C[j][i])

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

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

h, w = map(int, input().split())
ma = [ list(map(int,input().split(" "))) for i in range(10)]
sco = [ list(map(int,input().split(" "))) for i in range(h)]
a = csr_matrix(ma)
b = dijkstra(a)
ans = 0
for i in range(h):
  for j in range(w):
    num = sco[i][j]
    if num != -1:
      ans += b[num][1]
print(int(ans))

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

h,w = mi()
c = [[float('inf') for j in range(10)]for i in range(10)]

for i in range(10):
    cc = li()
    for j in range(10):
        c[i][j] = cc[j]



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

dp = [float("INF")]*(10)
dp[1] = 0
cnt = 0
while cnt <= 10:
    cnt += 1
    for i in range(10):
        for j in range(10):
            dp[j] = min(dp[j],dp[i]+C[j][i])

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

Solution (Python):
INF=10**18
n=10
h,w=map(int,input().split())
dist=[list(map(int,input().split())) for _ in range(n)]
a=[list(map(int,input().split())) for _ in range(h)]
for k in range(n):
  for i in range(n):
    for j in range(n):
      dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
ans=0
for i in range(h):
  for j in range(w):
    if a[i][j]==-1:continue
    ans+=dist[a[i][j]][1]
print(ans)

Solution (Python):
import sys

H, W = map(int, input().split())
C = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(10)]
A = [list(map(int, sys.stdin.readline().rsplit())) 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]

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

Solution (Python):
f=lambda:[*map(int,input().split())]
h,w=f()
r=range(10)
c=[f() for _ in r]
C=[0]*10
for _ in range(h):
  for i in f():
    if i>=0: C[i]+=1
for k in r:
  for i in r:
    for j in r:
      c[i][j]=min(c[i][j],c[i][k]+c[k][j])
print(sum(c[i][1]*C[i] for i in r))

Solution (Python):
f=lambda:[*map(int,input().split())]
h,w=f()
r=range(10)
c=[f() for _ in r]
C=[0]*10
for _ in range(h):
  for i in f():
    if i>=0: C[i]+=1
m=[c[i][1] for i in r]
for _ in r:
  for i in r:
    for j in r:
      m[i]=min(m[i],c[i][j]+m[j])
print(sum(m[i]*C[i] for i in r))

Solution (Python):
from collections import Counter
h, w = map(int, input().split())
C = [[0]*10 for _ in range(10)]
cost = []
for i in range(10):
    C[i] = 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])
costs = [C[i][1] for i in range(10)]

A = Counter()
for i in range(h):
    A += Counter(list(map(int,input().split())))

ans = 0
for key, val in A.items():
    if key!=-1:
        ans += val*costs[key]
print(ans)

Solution (Python):
import sys

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


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

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

    res = 0
    for h in range(H):
        for w in range(W):
            if grid[h][w] == -1 or grid[h][w] == 1:
                continue
            num = grid[h][w]
            res += cost[num][1]
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
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

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

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

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

a = [list(map(int,input().split())) for i in range(h)]
d1 = []
s = warshall_floyd(d)
for i in s:
  d1.append(i[1])

su = 0
for i in a:
  for j in i:
    if j!=-1:
      su += d1[j]
print(su)

Solution (Python):
def warshall_floyd():
    '''
    すべての頂点間の最短距離を求める
    '''
    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])


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

warshall_floyd()

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

print(res)

Solution (Python):
from heapq import heappush, heappop


def dijkstra(s):
    '''
    始点sから各頂点への最短距離を求める
    '''
    d = [float("inf")] * 10
    d[s] = 0
    used = [False] * 10
    used[s] = True
    edgelist = []

    for e in edge[s]:
        heappush(edgelist, e)

    while edgelist:
        cost, v = heappop(edgelist)
        if used[v]:
            continue
        d[v] = cost
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(edgelist, [e[0] + d[v], e[1]])

    return d


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

edge = [[] for _ in range(10)]
for i in range(10):
    for j in range(10):
        edge[i].append([c[i][j], j])
        edge[j].append([c[j][i], i]) 

dist = []
for i in range(10):
    dist.append(dijkstra(i))

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

print(res)

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import shortest_path
 
H, W, *t = map(int, open(0).read().split())
c = np.array(t[:100]).reshape((10, 10))
A = np.array(t[100:])
print(int(np.sum(shortest_path(c)[:, 1][A[A >= 0]])))

Solution (Python):
from numpy import *
from scipy.sparse.csgraph import *
H,W,*t=map(int,open(0).read().split())
c=array(t[:100]).reshape((10,10))
A=array(t[100:])
print(int(sum(shortest_path(c)[:,1][A[A>=0]])))

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

H, W, *t = map(int, open(0).read().split())
c = np.array(t[:100]).reshape((10, 10))
A = np.array(t[100:])
print(int(np.sum(shortest_path(c)[:, 1][A[A >= 0]])))

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

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

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

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

print(ans)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall, csgraph_from_dense
import sys
input = sys.stdin.readline

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

G = csgraph_from_dense(c)
d = floyd_warshall(G).astype(int)

ans = 0

for l in a:
    for ai in l:
        if ai == -1:
            continue
        ans += d[ai][1]

print(ans)

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

H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(10)]
warshall_floyd()
res = 0
for _ in range(H):
    A = list(map(int, input().split()))
    res += sum(C[a][1] for a in A if a != -1)
print(res)

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

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), *ca = [list(map(int, l.split())) for l in open(0)]

ccc = ca[:10]
aaa = ca[10:]

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

costs = [cc[1] for cc in ccc]

tmp = 0
for aa in aaa:
    for a in aa:
        if a == -1:
            pass
        else:
            tmp += costs[a]

print(tmp)

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

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


d=[0]*10
for start in range(10):

    
    distance=grid[start]

    
    visited=[0] * 10
    visited[start] = 1
    size = 1

    while size<10:
        min_distance = 10**9
        for i in range(10):
            if visited[i]==0 and distance[i] <min_distance:
                min_distance = distance[i]
                v = i

        visited[v] = 1
        size+=1

        for x in range(10):
            if distance[x] > distance[v] + grid[v][x]:
                distance[x] = distance[v] + grid[v][x]

    d[start]=distance[1]

ans=0
for i in range(H):
    for j in range(W):
        if Wall[i][j]==-1:
            continue
        else:
            ans+=d[Wall[i][j]]

print(ans)

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

Solution (Python):
import heapq
INF = 10**10


def dijkstra(s, G):
    d = [INF] * len(G)
    d[s] = 0
    q = []
    heapq.heapify(q)
    heapq.heappush(q, (0, s))
    while len(q) > 0:
        shortest, v = heapq.heappop(q)
        if d[v] < shortest:
            continue
        for e in G[v]:
            to, cost = e
            if d[to] > d[v] + cost:
                d[to] = d[v] + cost
                heapq.heappush(q, (d[to], to))
    return d


H, W = map(int, input().split())
G = [[] for _ in range(10)]
for i in range(10):
    adj = list(map(int, input().split()))
    for j, cost in enumerate(adj):
        
        G[j].append((i, cost))
shortest_d = dijkstra(1, G)
ans = 0
for _ in range(H):
    for x in list(map(int, input().split())):
        if x == -1:
            continue
        ans += shortest_d[x]
print(ans)

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

Solution (Python):
import heapq
INF = 10**10

def dijkstra(n, edges, s):
    """
    input
        n : 頂点数
        edges : リスト(始点, 終点, コスト)
        s : 始点
    output
        d : 始点からの最短距離
    """
    d = [INF] * n
    used = [False] * n
    d[s] = 0
    used[s] = True
    edgelist = []
    
    for v, c in edges[s]:
        
        
        heapq.heappush(edgelist, (c, v))
    
    while len(edgelist):
        
        c_min, v_min = heapq.heappop(edgelist)
        
        if used[v_min]:
            continue
        
        d[v_min] = c_min
        used[v_min] = True
        for v, c in edges[v_min]:
            if not used[v]:
                heapq.heappush(edgelist, (c+c_min, v))
    return d
h,w = map(int, input().split())
cij = []
for i in range(10):
    row = list(map(int, input().split()))
    cij.append(row)
A = []
for i in range(h):
    row = list(map(int, input().split()))
    A.append(row)
edges = [[] for i in range(10)]
for i in range(10):
    for j in range(10):
        if i != j:
            edges[i].append((j, cij[i][j]))

ds = []
for i in range(10):
    costs = dijkstra(10,edges,i)
    ds.append(costs[1])
ans = 0
for r in A:
    for e in r:
        if e == -1: continue
        ans += ds[e]
print(ans)

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

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

cost = floyd_warshall(graph)
cost = cost.astype(int)

arr = np.array([list(map(int, input().split())) for _ in range(h)])
arr = arr.flatten()

ans = 0
for x in arr:
    if x == -1:
        continue
    else:
        ans += cost[x][1]

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

Solution (Python):

import sys


def warshall_floyd(A):
    
    l = len(A)
    for k in range(l):
        for i in range(l):
            for j in range(l):
                A[i][j] = min(A[i][j], A[i][k] + A[k][j])
    return A


def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):
    c = warshall_floyd(c)
    cost = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] != -1:
                cost += c[A[h][w]][1]
    print(cost)
    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())
C = [list(map(int, input().split())) for i in range(10)]
A = [list(map(int, input().split())) for i in range(H)]

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

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

print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    import networkx as nx
    h, w = map(int, readline().split())
    G = nx.DiGraph()

    for i in range(10):
        costs = list(map(int, readline().split()))
        for j, cost in enumerate(costs):
            if i != j:
                G.add_edge(i, j, weight=cost)

    d = nx.algorithms.floyd_warshall(G)

    counter = Counter()
    for _ in range(h):
        nums = list(map(int, readline().split()))
        counter.update(nums)
    ans = 0
    for num in range(10):
        ans += counter[num] * d[num][1]

    print(ans)


if __name__ == '__main__':
    main()

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

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

Solution (Python):
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


def warsharll_floyd(c):
    n = len(c)
    for k in range(n):  
        for i in range(n):  
            for j in range(n):  
                
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])
    return c


def main():
    h, w = LI()
    c = LIR(10)
    a = LIR(h)
    
    
    costs = warsharll_floyd(c)
    ans = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] in {-1, 1}:
                continue
            else:
                ans += costs[a[i][j]][1]
    print(ans)


main()

Solution (Python):
n,m = map(int,input().split())
dist = [list(map(int,input().split())) for i in range(10)]
dist.append([0]*10)
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])
ans = 0
for i in range(n):
  a = list(map(int,input().split()))
  for j in a:
    ans += dist[j][1]
print(ans)

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines




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

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

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

mp=[[0]*10 for i in range(10)]

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

a=[[] for i in range(h)]

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

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

ans = 0
for i in range(h):
    wall = list(map(int, input().split()))  
    for item in wall:
        if item < 0:
            continue
        ans += power[item][1]  
print(ans)

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

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

ans = 0
for i in range(h):
    wall = list(map(int, input().split()))  
    for item in wall:
        if item < 0:
            continue
        ans += power[item][1]  
print(ans)

Solution (Python):


import sys
input=sys.stdin.readline

def main():
    inf=10**6
    H,W=map(int,input().split())
    dp=[[inf]*10 for i in range(10)]
    for i in range(10):
        row=list(map(int,input().split()))
        for j in range(10):
            dp[i][j]=row[j]
    
    cnt=[0]*10
    for i in range(H):
        row=list(map(int,input().split()))
        for a in row:
            if a!=-1:
                cnt[a]+=1
                
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if dp[i][k]<inf and dp[k][j]<inf:
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
                    
    ans=0
    for i in range(10):
        ans+=dp[i][1]*cnt[i]
        
    print(ans)
    
                
    
    
if __name__=="__main__":
    main()

Solution (Python):
import sys
read = sys.stdin.read
from itertools import chain
from collections import Counter
def main():
    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())
    n = 10
    d = [[10**9] * 10 for _ in range(10)]
    for i1 in range(10):
        row = tuple(map(int, input().split()))
        for i2 in range(10):
            d[i1][i2] = row[i2]
    res = warshall_floyd(d)
    hw = [list(map(int, input().split())) for _ in range(h)]
    hw1d = chain.from_iterable(hw)
    hw1dc = Counter(hw1d)
    r = 0
    for j1 in range(10):
        r += hw1dc[j1] * res[j1][1]
    print(r)

if __name__ == '__main__':
    main()

Solution (Python):
H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(10)]
A = [list(map(int, input().split())) for _ in range(H)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            C[i][j] = min(C[i][j], C[i][k] + C[k][j])
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] >= 0:
            ans += C[A[i][j]][1]
print(ans)

Solution (Python):
INF = 2**100

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

num = [0] * n
for i in range(h):
    b = [int(j) for j in input().split()]
    for j in b:
        if j != -1:
            num[j] += 1

print(sum([d[i][1]*num[i] for i in range(n)]))

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

H,W = map(int,readline().split())
G = [None] * 10

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

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

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

print(ans)

Solution (Python):






from collections import Counter
from copy import copy

import sys
input = sys.stdin.readline

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

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

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

cnt = Counter(A)

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

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


print(res)

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 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())
ans=[float("inf") for i in range(10)]
p=[]
a=[]
for i in range(10):
    p.append(list(map(int,input().split())))
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):
            p[j][k]=min(p[j][i]+p[i][k],p[j][k])
ans=float("inf")
tmp=0
for j in range(h):
    for k in range(w):
        if a[j][k]!=-1:
            tmp+=p[a[j][k]][1]
print(tmp)

Solution (Python):
from heapq import heappush, heappop

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

nums = []
for _ in range(h):
    nums += [int(i) for i in input().split()]


def dijkstra(s=1, c=c):
    INF = float('inf')

    d = {i: INF for i in range(10)}
    d[-1] = 0
    d[s] = 0

    queue = []
    heappush(queue, (0, s))

    while queue:
        di, v = heappop(queue)
        for i in range(10):
            dtmp = d[v] + c[i][v]
            if dtmp < d[i]:
                d[i] = dtmp
                heappush(queue, (dtmp, i))

    return d


magic = dijkstra()
answer = sum(magic[i] for i in nums)
print(answer)

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


H, W = map(int, input().split())
G = [[int(i) for i in input().split()] for j in range(10)]
G = csgraph_from_dense(G)

dist = floyd_warshall(G)
ans = 0
for h in range(H):
    line = [int(i) for i in input().split()]
    for w in range(W):
        if line[w] == -1:
            continue
        ans += dist[line[w]][1].astype(int)

print(ans)

Solution (Python):
def main():
    h, w, *ca = map(int, open(0).read().split())
    it = zip(*[iter(ca[:100])] * 10)
    *c, = map(lambda i: list(i), it)
    a = ca[100:]

    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
    cost = {i: c[i][1] for i in [0, 2, 3, 4, 5, 6, 7, 8, 9]}
    cost.update({-1: 0, 1: 0})

    for i in a:
        ans += cost[i]

    print(ans)


if __name__ == '__main__':
    main()