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):
from scipy.sparse import*
a=[list(map(int,t.split()))for t in open(0)]
print(int(sum(csgraph.dijkstra(csr_matrix(a[1:11]))[[i<0 or i for i in sum(a[11:],[])],1])))

Solution (Python):
from scipy.sparse import*
a=[list(map(int,t.split()))for t in open(0)]
print(int(sum(csgraph.dijkstra(csr_matrix(a[1:11]))[[j<0 or j for i in a[11:]for j in i],1])))

Solution (Python):
import heapq
def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d
_,*a = [list(map(int,t.split())) for t in open(0)]
n = 10
edge = [[] for _ in range(n)]
for i in range(n):
    for j in range(n):
        edge[i].append((a[i][j],j))
c = [dijkstra_heap(i)[1] for i in range(n)]+[0]
print(sum(c[j] for i in a[n:] for j in i))

Solution (Python):
from scipy.sparse import*
_,*a=[list(map(int,t.split()))for t in open(0)]
print(int(sum(csgraph.dijkstra(csr_matrix(a[:10]))[[j<0 or j for i in a[10:]for j in i],1])))

Solution (Python):
from scipy.sparse import*
_,*a=[list(map(int,t.split()))for t in open(0)]
print(int(sum(csgraph.dijkstra(csr_matrix(a[:10]))[[j for i in a[10:]for j in i if j>=0],1])))

Solution (Python):
from scipy.sparse import*
_,*a=[list(map(int,t.split()))for t in open(0)]
c=csgraph.dijkstra(csr_matrix(a[:10]))
print(int(sum(c[j][1]for i in a[10:]for j in i if j>=0)))

Solution (Python):
from scipy.sparse import*
*a,=map(int,open(0).read().split())
c=csgraph.dijkstra(csr_matrix([a[i:i+10]for i in range(2,99,10)]))
print(int(sum(c[i][1]for i in a[102:]if i>=0)))

Solution (Python):
from scipy.sparse import*
*a,=map(int,open(0).read().split())
c=csgraph.dijkstra(csr_matrix([a[i:i+10]for i in range(2,102,10)]))
print(int(sum(c[i][1]for i in a[102:]if i>=0)))

Solution (Python):
from scipy.sparse import*
h,w,*a=map(int,open(0).read().split())
c=csgraph.dijkstra(csr_matrix([a[i*10:-~i*10]for i in range(10)]))
print(int(sum(c[i][1]for i in a[100:]if i>=0)))

Solution (Python):
from scipy.sparse import*
h,w,*a=map(int,open(0).read().split())
c=csgraph.dijkstra(csr_matrix([a[i*10:-~i*10]for i in range(10)]))
print(int(sum([c[i][1]for i in a[100:]if i>=0])))

Solution (Python):
from scipy.sparse import*
i=lambda:list(map(int,input().split()))
h,w=i()
c=csgraph.dijkstra(csr_matrix([i()for _ in[0]*10]))
print(int(sum(c[j][1]for i in eval('i(),'*h)for j in i if j>=0)))

Solution (Python):


from scipy.sparse.csgraph import shortest_path 
from scipy.sparse import csr_matrix
 
from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul,itemgetter
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)

 
def main():
    h,w=map(int,input().split())
    grid=[list(map(int,input().split()))for i in range(10)]
    
    c=0
    grid=shortest_path(csgraph=csr_matrix(grid))
    for i in range(h):
        for j in map(int,input().split()):
            if j!=-1:
                c+=grid[j][1]

    print(int(c))
if __name__ == '__main__':
    main()

Solution (Python):


def main():
    high, width = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(10)]
    inf = 10 ** 10
    kyori = [inf for i in range(10)]
    kyori[1] = 0

    itta = set()
    itta.add(1)
    while len(itta) < 10:
        now_kyori = inf
        ind = -1

        for ele_now in itta:
            for ele_next in range(10):
                if ele_now == ele_next or ele_next in itta:
                    continue
                length = kyori[ele_now] + data[ele_next][ele_now]
                if length < now_kyori:
                    now_kyori = length
                    ind = ele_next
        itta.add(ind)
        kyori[ind] = now_kyori


    ans = 0
    for i in range(high):
        get_data = list(map(int, input().split()))
        for ele in get_data:
            if ele == -1 or ele == 1:
                continue
            ans += kyori[ele]

    print(ans)



if __name__ == '__main__':
    main()

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

L = [0] * 10

for i in range(10):
  L[i] = c[i][1]

for i in range(10):
  for j in range(10):
    if j == 1:
      continue
    for k in range(10):
      if L[j] + c[k][j] < L[k]:
        L[k] = L[j] + c[k][j]

ans = 0
for l in A:
  for x in l:
    if x != -1:
      ans += L[x]

print(ans)

Solution (Python):
from heapq import *
h,w=map(int,input().split())
g=[[] for i in range(10)]
for i in range(10):
    l=list(map(int,input().split()))
    for j in range(10):
         g[i].append([l[j],j])
d={}
for i in range(10):
    q=[[0,i]]
    heapify(q)
    l=[-1 for i in range(10)]
    while l[1]==-1:
        c,t=heappop(q)
        if(l[t]==-1):
            l[t]=c
            for j in g[t]:
                C,T=j
                if(l[T]==-1):
                    heappush(q,[c+C,T])
    d[i]=l[1]           
ans=0
for i in range(h):
    l=list(map(int,input().split()))
    for j in l:
        ans+=d.get(j,0)
print(ans)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
h,w=map(int,input().split())
n=10
d=[]
for i in range(n):
    d.append(list(map(int,input().split())))
a=[]
for i in range(h):
    a.append(list(map(int,input().split())))

d=floyd_warshall(d).tolist()
cnt=0
for i in range(h):
    for j in range(w):
        if a[i][j]==-1:continue
        cnt+=d[a[i][j]][1]
print(int(cnt))

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

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


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

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

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


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

Solution (Python):


H,W = [int(i) for i in 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)]


dist = c
n=10

for k,dk in enumerate(dist):
    for di in dist:
        for j in range(n):
            if di[j] > di[k]+ dk[j]:
                di[j] = di[k]+ dk[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):


H,W = [int(i) for i in 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)]


dist = c
n=10

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


H,W = [int(i) for i in 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)]


dist = c
n=10

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

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

count=[0]*10
for i in range(H):
    l=list(map(int,input().split()))
    for j in range(10):
        count[j]+=l.count(j)
ans=0
for i in range(10):
    ans+=count[i]*c[i][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)]

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

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

res = 0
for i in range(H):
    for j in range(W):
        if INM[i][j] != -1:
            res += MAT[INM[i][j]][1]

print(res)

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

e_list = [[] for i in range(10)]
for i in range(10):
    c = list(map(int,input().split()))
    for j in range(10):
        if i!=j:
            e_list[i].append([j,c[j]])

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




import heapq

d_list = []
N=10
for i in range(10):
    vi = i
    min_d_list = [10**27 for i in range(N)]
    min_d_list[vi] = 0
    prev_list = [-1 for i in range(N)]
    q = []
    for i in range(N):
        heapq.heappush(q,[min_d_list[i],i])

    while len(q)>0:
        d,v = heapq.heappop(q)
        for e in e_list[v]:
            v1,d1=e
            if min_d_list[v1]>d+d1:
                min_d_list[v1]=d+d1
                prev_list[v1]=v
                heapq.heappush(q,[d+d1,v1])
    d_list.append(min_d_list)
score=0
for i in range(H):
    for j in range(W):
        if A[i][j]!=-1:
            score+=d_list[A[i][j]][1]

print(score)

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

ct=0
for i in range(h):
  for j in range(w):
    if a[i][j]>=0:
      ct+=ansL[a[i][j]]
print(ct)

Solution (Python):
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):
                C[i][j] = min(C[i][j], C[i][k] + C[k][j])
    ans = 0
    for h in range(H):
        for a in A[h]:
            if a >= 0:
                ans += C[a][1]
    print(ans)


main()

Solution (Python):
h, w = map(int, input().split())
inf = 10**8
d = [[inf for _ in range(10)] for _ in range(10)]
c = []
for i in range(10):
    c = list(map(int, input().split()))
    for j in range(10):
        d[i][j] = c[j]



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

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

print(ans)

Solution (Python):
h,w=map(int,input().split())
c=[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):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])
for i in range(10):
    for j in range(10):
        for k in range(10):
            c[i][j]=min(c[i][j],c[i][9-k]+c[9-k][j])
for i in range(10):
    for j in range(10):
        for k in range(10):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])
l=[]
for i in range(h):
    l.extend(list(map(int,input().split())))
x=0
for i in range(10):
    x+=c[i][1]*l.count(i)
print(x)

Solution (Python):
H, W = map(int, input().split())
cs =[list(map(int, input().split())) for _ in range(10)]
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
cs = warshall_floyd(cs)
As = [list(map(int, input().split())) for _ in range(H)]
ans = 0
for A in As:
    for a in A:
        if a != -1:
            ans += cs[a][1]
print(ans)

Solution (Python):

import sys
import heapq
from collections import Counter
INF = float("inf")




class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])

        pass


def shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):
    g = Graph(10)
    
    for i in range(10):
        for j in range(10):
            g.add_edge([j, i, c[i][j]])

    c = Counter()
    for a in A:
        c.update(a)

    
    dist, prev = shortestPath(g, 1)
    
    
    ans = 0
    for key in c:
        if key == 1 or key == -1:
            continue
        ans += dist[key]*c[key]

    print(ans)
    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):

from Queue import PriorityQueue
H,W=map(int,raw_input().split())
c=[]
for i in range(10):
    c.append(map(int,raw_input().split()))

A=[]
for i in range(H):
    A.append(map(int,raw_input().split()))
cost=[-1]*10
cost[1]=0
pq=PriorityQueue()
for i in range(0,10): 
    if i!=1:pq.put((c[i][1],i))
while not pq.empty():
    co,po=pq.get()
    if cost[po]!=-1:continue
    cost[po]=co
    for i in range(0,10):
        if cost[i]==-1:
            pq.put((c[i][po]+co, i))

ans=0
for L in A:
    for l in L:
        if l!=-1:ans+=cost[l]
print(ans)

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

if __name__=="__main__":
    sol()

Solution (Python):
from itertools import product


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 = [{} for _ in range(10)]
for i, j in product(range(10), repeat=2):
    G[i][j] = c[i][j]
INF = 10**10


def warshall_floyd(G):
    dp = [
        [
            0 if i == j else
            G[i][j] if j in G[i] else
            INF
            for j in range(len(G))
        ]
        for i in range(len(G))
    ]
    for k in range(len(G)):
        for i in range(len(G)):
            for j in range(len(G)):
                dp[i][j] = (
                    dp[i][j] if dp[i][k] == INF or dp[k][j] == INF else
                    min(dp[i][j], dp[i][k] + dp[k][j])
                )
    return dp


dp = warshall_floyd(G)

ans = sum(
    dp[x][1]
    for a in A
    for x in a
    if x >= 0
)


print(ans)

Solution (Python):
def sol():
    h,w=map(int,input().split())
    c=[]
    for i in range(10):
        l=[int(i) for i in input().split()]
        c.append(l)
    a=[]
    for i in range(h):
        l=[int(i) for i in input().split()]
        a.append(l)
    p=[0]*10
    for i in range(10):
        if i==1: continue
        d=[1003]*10
        d[i]=0
        q=set([i])
        while 1:
            if len(q)==0: break
            x=q.pop()
            for j in range(10):
                if i==j: continue
                if (d[j]>d[x]+c[x][j]):
                    d[j]=d[x]+c[x][j]
                    q.add(j)
        p[i]=d[1]
    ans=0
    for i in range(h):
        for j in range(w):
            if a[i][j]==-1: pass
            else: ans+=p[a[i][j]]
    print(ans)

if __name__=="__main__":
    sol()

Solution (Python):
h,w=map(int,input().split())
c=[]
for i in range(10):
    l=[int(i) for i in input().split()]
    c.append(l)
a=[]
for i in range(h):
    l=[int(i) for i in input().split()]
    a.append(l)
p=[0]*10
for i in range(10):
    if i==1: continue
    d=[1003]*10
    d[i]=0
    q=set([i])
    while 1:
        if len(q)==0: break
        x=q.pop()
        for j in range(10):
            if i==j: continue
            if (d[j]>d[x]+c[x][j]):
                d[j]=d[x]+c[x][j]
                q.add(j)
    p[i]=d[1]
ans=0
for i in range(h):
    for j in range(w):
        if a[i][j]==-1: pass
        else: ans+=p[a[i][j]]
print(ans)

Solution (Python):
from itertools import product


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 = [{} for _ in range(10)]
for i, j in product(range(10), repeat=2):
    G[i][j] = c[i][j]
INF = 10**10


def warshall_floyd(G):
    dp = [
        [
            0 if i == j else
            G[i][j] if j in G[i] else
            INF
            for j in range(len(G))
        ]
        for i in range(len(G))
    ]
    for k in range(len(G)):
        for i in range(len(G)):
            for j in range(len(G)):
                dp[i][j] = (
                    dp[i][j] if dp[i][k] == INF or dp[k][j] == INF else
                    min(dp[i][j], dp[i][k] + dp[k][j])
                )
    return dp


dp = warshall_floyd(G)

ans = sum(
    dp[x][1]
    for a in A
    for x in a
    if x >= 0
)


print(ans)

Solution (Python):
def warshall_floyd(c):
    d = {}

    for i in range(10):
        for j in range(10):
            d[i, j] = c[i][j]
    
    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

def answer(h, w, c, a):
    ans = 0
    d = warshall_floyd(c)
    count = []

    for i in range(10):
        count.append(0)
    
    for i in range(h):
        for j in range(w):
            if a[i][j] != -1:
                count[a[i][j]] += 1

    for i in range(10):
        ans += d[i, 1] * count[i]

    return ans


[h, w] = list(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())))

print(str(answer(h, w, c, a)))

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
h,w=map(int,input().split())
table=[[0]*10 for i in range(10)]
for i in range(10):
  C=[int(i) for i in input().split()]
  for j in range(10):
    table[i][j]=C[j]
d=floyd_warshall(csgraph=table, directed=True, return_predecessors=False)
ans=0
for i in range(h):
  A=[int(i) for i in input().split()]
  for a in A:
    if a!=-1:
      ans+=int(d[a][1])
print(ans)

Solution (Python):
H,W=map(int, input().split())
c=[list(map(int,input().split())) for i in range(10)]
A=[list(map(int,input().split())) for i in range(H)]
def dfs(n,tcost,depth):
    for i in range(10):
        if cost[i]>tcost+c[i][n]:
            cost[i]=tcost+c[i][n]
            if depth<10:
                dfs(i,cost[i],depth+1)
cost=[10**4]*11
cost[1]=0
cost[-1]=0
dfs(1,0,0)
ans=0
for h in range(H):
    for w in range(W):
        ans+=cost[A[h][w]]
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)]

from scipy.sparse.csgraph import floyd_warshall
cost=floyd_warshall(c)

total = 0
for i in range(h):
    for j in range(w):
        if a[i][j] != -1:
            start = a[i][j]
            d = cost[start][1]
            total += int(d)

print(total)

Solution (Python):
H,W = [ int(it) for it in input().split() ]
li = [ [ int(it) for it in input().split() ] for i in range(10) ]

from copy import deepcopy

for _ in range(19):
  li2 = deepcopy(li)
  for i in range(10):
    for j in range(10):
      for k in range(10):
        li2[i][j] = min( li2[i][j] , li[i][k]+li[k][j] )
  li = li2

gr = []
for i in range(H):
  gr.extend([ int(it) for it in input().split() ])
  
import collections  as cols
ccc = cols.Counter(gr)
cost = 0
for k,v in ccc.items():
  if (k!=-1):
    cost += v*li[k][1]
print ( cost )

Solution (Python):
import sys

import numpy as np
from scipy.sparse.csgraph import dijkstra

sys.setrecursionlimit(10000)
INF = float('inf')

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

mp = dijkstra(C, directed=True)[:, 1]
ans = 0
for n in range(10):
    ans += mp[n] * np.sum(A == n)
print(int(round(ans)))

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

Solution (Python):
from functools import reduce
import math
import copy

def main():
    
    
    
    

    
    
    
    
    
    

    
    

    
    
    
    
    
    
    
    
    
    INF = float("inf")

    
    MOD = 10**9+7
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

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

    d = copy.deepcopy(c)
    for k in range(10):
        for i in range(10):
            for j in range(10):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] != -1:
                ans += d[A[i][j]][1]
    print(ans)
    
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)]
memo = {}
def dfs(nv,vl,cost):
    if nv==1:
        return cost
    if nv in memo.keys():
        return cost+memo[nv]
    vl_ = vl.copy()
    vl_.append(nv)
    ret = []
    for i in range(10):
        if not i in vl_:
            ret.append(dfs(i,vl_,cost+c[nv][i]))
    return min(ret)
cost = []
for i in range(10):
    memo[i] = dfs(i,[],0)
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j]!=-1:
            ans += memo[a[i][j]]
print(ans)

Solution (Python):


import itertools
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford, floyd_warshall


H, W = [int(i) for i in input().split()]

rows = []
cols = []
weights = []

"""
for _ in range(M):
    
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(a)
"""
for i in range(10):
    
    c = [int(j) for j in input().split()]
    
    for j in range(10):
        rows.append(i)
        cols.append(j)
        weights.append(c[j])


graph = coo_matrix((weights, (cols, rows)), shape=(10, 10)).tocsr()


d2 = floyd_warshall(graph, directed=True, unweighted=False)


ans = 0

for i in range(H):
    a = [int(_) for _ in input().split()]
    for j in a:
        if j != -1:
            ans += d2[1][j]

print(int(ans))

Solution (Python):


import itertools
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford


H, W = [int(i) for i in input().split()]

rows = []
cols = []
weights = []

"""
for _ in range(M):
    
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(a)
"""
for i in range(10):
    
    c = [int(j) for j in input().split()]
    
    for j in range(10):
        rows.append(i)
        cols.append(j)
        weights.append(c[j])


graph = coo_matrix((weights, (cols, rows)), shape=(10, 10)).tocsr()

d1 = dijkstra(graph, indices=1, directed=True, unweighted=False)



ans = 0

for i in range(H):
    a = [int(_) for _ in input().split()]
    for j in a:
        if j != -1:
            ans += d1[j]

print(int(ans))

Solution (Python):
h,w = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
a = [list(map(int, input().split())) for _ in range(h)]
r = [c[x][1] for x in range(10)] + [0]
done = [0]*10
done[1] = 1
ans = 0
while not all(done):
  mm = 10**5
  cur = -1
  for i in range(10):
    if not done[i] and r[i]<mm:
      mm = r[i]
      cur =  i
  done[cur] = 1
  for x in range(10):
    if r[x] > c[x][cur] + r[cur]:
      r[x] = c[x][cur] + r[cur]
for x in a:
  for y in x:
    ans += r[y]
print(ans)

Solution (Python):
H, W = map(int, input().split())
INF = 2 ** 63 - 1
d = []
for i in range(10):
    d.append(list(map(int, input().split())))
A = []
for i in range(H):
    A += list(map(int, input().split()))
for k in range(10):
    for i in range(10):
        for j in range(10):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
ans = 0
for i in range(len(A)):
    if A[i] == -1:
        continue
    ans += d[A[i]][1]
print(ans)

Solution (Python):
from collections import Counter
from functools import reduce

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

A=Counter(map(int, reduce(lambda a,b: a+b, [input().split() for _ in range(H)])))
print(sum([c[i][1] * A[i] for i in range(10) if i in A]))

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