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


def main():
    H, W = map(int, input().split())

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

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

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

    print(sum(map(lambda i: c[i][1] if i >= 0 else 0, A)))

if __name__ == '__main__':
    main()

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

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

print(ans)

Solution (Python):
def Pto1(C):
    d = C.copy()
    for q in range(0,10):
        for i in range(0,10):
            for j in range(0,10):
                d[i][j] = min(d[i][j], d[i][q]+d[q][j])
    return [d[0][1],d[1][1],d[2][1],d[3][1],d[4][1],d[5][1],d[6][1],d[7][1],d[8][1],d[9][1]]

H,W = map(int,input().split(' '))
C = []
for i in range(0,10):
    cline = list(map(int,input().split(' ')))
    C.append(cline)
C1 = Pto1(C)
A = []
for j in range(0,H):
    aline = list(map(int,input().split(' ')))
    A.append(aline)
h=0
w=0
counter=[0]*10
while h<H:
    w=0
    while w<W:
        if A[h][w]>=0:
            counter[A[h][w]] += 1
        w+=1
    h+=1
Cmin = 0
for k in range(0,10):
    Cmin += C1[k]*counter[k]
print(int(Cmin))

Solution (Python):

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

c = [[0 for i in range(10)] for j in range(10)]
for i in range(10):
    line = list(map(int, input().split()))
    for j in range(10):
        c[i][j] = line[j]

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

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

print(total)

Solution (Python):
if __name__ == "__main__":
    h, w = list(map(int, input().split()))
    cost = {}
    for i in range(10):
        for j, c in enumerate(map(int, input().split())):
            cost[(i, j)] = c

    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)])
    
    cost[(-1, 1)] = 0
    
    print(sum([sum(map(lambda x: cost[(x, 1)], map(int, input().split()))) for i in range(h)]))

Solution (Python):

import copy
import collections

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

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

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

mincost = {}
for i in range(10):
    mincost[i] = c[i][1]

copy_mincost = {}
while mincost != copy_mincost:
    copy_mincost = copy.deepcopy(mincost)
    for i in range(10):
        for j in range(10):
            if mincost[j] > mincost[i] + c[j][i]:
                mincost[j] = mincost[i] + c[j][i]

co = collections.Counter(A)
ans = 0

for i in range(0, 10):
    ans += co[i] * mincost[i]

print(ans)

Solution (Python):
import math

INF=1000000000

cs=[[INF for i in range(10)]for j in range(10)]
nums=[0]*10 




temp=list(map(int,input().split(" ")))
H=temp[0]
W=temp[1]
for i in range(10):
    temp=list(map(int,input().split(" ")))
    for j in range(10):
        cs[i][j]=temp[j] 

for i in range(H):
    temp=list(map(int,input().split(" ")))
    for j in range(W):
        if temp[j]!=-1:
            nums[temp[j]]+=1

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

result=0
for i in range(10):
    result+=(nums[i]*cs[i][1])
print(result)

Solution (Python):
import math

def do():
    cs=[[0 for i in range(10)]for j in range(10)]
    
    INF=10000000
    node_num=10
    unsearch=list(range(node_num)) 
    cos=[INF]*node_num 
    cos[1]=0
    
    nums=[0]*10 

    temp=list(map(int,input().split(" ")))
    H=temp[0]
    W=temp[1]
    for i in range(10):
        temp=list(map(int,input().split(" ")))
        for j in range(10):
            cs[j][i]=temp[j]

    for i in range(H):
        temp=list(map(int,input().split(" ")))
        for j in range(W):
            if temp[j]!=-1:
                nums[temp[j]]+=1

    def get_target_min_index(min_index,distance,unsearch):
        start=0
        while True:
            index=distance.index(min_index,start)
            found=index in unsearch
            if found:
                return index
            else:
                start = index+1

    while len(unsearch)!=0:
        posible_min_distance=INF
        for node_index in unsearch:
            if posible_min_distance > cos[node_index]:
                posible_min_distance=cos[node_index]
        target_min_index=get_target_min_index(posible_min_distance,cos,unsearch)
        unsearch.remove(target_min_index)
        target_edge=cs[target_min_index] 

        for index,route_dis in enumerate(target_edge):
             
             if route_dis !=0:
                 if cos[index] > cos[target_min_index] + route_dis:
                     cos[index]=cos[target_min_index] + route_dis


    result=0
    for i in range(10):
        result+=(nums[i]*cos[i])
    print (result)

        


if __name__=="__main__":
    do()

Solution (Python):

import queue
INF = 10000000


G = []
kabe = []
H, W = map(int, input().split())


for i in range(10):
    G.append(list(map(int, input().split())))

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

lenList = [INF for i in range(10)]

q = queue.PriorityQueue()

def dijkstra():
    global G
    global q
    global lenList
    
    x = q.get()
    
    if lenList[x[1]] != INF:
        return
    
    
    lenList[x[1]] = x[0]

    
    for i in range(10):
        if lenList[i] == INF:
            q.put([x[0] + G[i][x[1]], i])


q.put([0, 1])
while not(q.empty()):
    dijkstra()

sum = 0

for i in range(H):
    for j in range(W):
        if kabe[i][j] != -1:
            sum += lenList[kabe[i][j]]

print(sum)

Solution (Python):

import queue
INF = 10000000

q = queue.PriorityQueue()


G = []
kabe = []
H, W = map(int, input().split())


for i in range(10):
    G.append(list(map(int, input().split())))

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

lenList = [INF for i in range(10)]

def bfs():
    global G
    global q
    global lenList
    
    x = q.get()
    
    while lenList[x[1]] != INF:
        return
    
    
    lenList[x[1]] = x[0]

    
    for i in range(10):
        if lenList[i] == INF:
            q.put([x[0] + G[i][x[1]], i])


q.put([0, 1])
while not(q.empty()):
    bfs()

sum = 0

for i in range(H):
    for j in range(W):
        if kabe[i][j] != -1:
            sum += lenList[kabe[i][j]]

print(sum)

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

Solution (Python):
h,w=map(int,input().split())
c=[[int(x) for x in input().split()] for _ in [0]*10]
a="".join([input() for _ in [0]*h])
nokori = [0,2,3,4,5,6,7,8,9]
while nokori:
    thiscost = 10**3
    for i in nokori:
        if c[i][1] <= thiscost:
            argmin = i
            thiscost = c[i][1]
    nokori.remove(argmin)
    for i in nokori:
        c[i][1] = min(c[i][1],c[i][argmin]+c[argmin][1])
c = c
ans = 0
for num in "023456789":
    ans += c[int(num)][1]*a.count(num)
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)]
ans=0

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

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):
H, W = map(int, raw_input().split())
c = [map(int, raw_input().split()) for _ in range(10)]
A = [map(int, raw_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])

print sum(sum(c[a][1] if a >= 0 else 0 for a in aa) for aa in A)

Solution (Python):
from collections import defaultdict
import heapq
INF = 1e9

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

n = 10
adj_matrix = []

for i in range(n):
    c = list(map(int, input().split()))
    adj_matrix.append(c)

Adj_list = defaultdict(set)

for i in range(n):
    for j in range(n):
        Adj_list[i].add((j, adj_matrix[i][j]))


def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)]
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u]+c, v))

    return d

ans = INF
t_dis = 0

table = {}
for i in range(n):
    table[i] = dijkstra(n, i)


t_dis = 0

for i in range(H):
    l = list(map(int, input().split()))
    for j in range(W):
        if l[j] != -1:
            t_dis += table[l[j]][1]
            
print(t_dis)

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):
            c1 = c[i][j]
            c2 = c[i][k] + c[k][j]
            if c1 > c2:
                c[i][j] = c2

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

minimum_cost = [0 for i in range(10)]
for s in range(10):
    g =1 
    md = [2000 for i in range(10)]
    md[s] = 0
    flag = [0 for i in range(10)]
    while flag[g] != 1:

        mikakutei_min = min([md[j] for j in range(10) if flag[j]==0])
        for v in range(10):
            if (flag[v] == 0 and md[v] == mikakutei_min):
                flag[v] = 1
        for j in [j for j in range(10) if flag[j] == 0]:
            for i in [i for i in range(10) if flag[i] == 1]:
                if md[j] > md[i] + c[i][j]:
                    md[j] = md[i] + c[i][j]
    minimum_cost[s] = md[g]
        

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

Solution (Python):
import numpy as np
from collections import Counter
H, W = map(int, input().split())
c = [list(map(int, input().split())) for i in range(10)]
A = np.array([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):
			tmp_dist = c[i][k] + c[k][j]
			if c[i][j] > tmp_dist:
				c[i][j] = tmp_dist
print(sum(c[k][1] * v for k, v in Counter(A[A != -1]).items()))

Solution (Python):
import math
st=input().split()
H=int(st[0]);W=int(st[1])
c=[[0 for i in range(10)] for i in range(10)]
A=[[0 for i in range(W)]for i in range(H)]
for i in range(10):
    st=input().split()
    for j in range(10):
        c[i][j]=int(st[j])
for i in range(H):
    st=input().split()
    for j in range(W):
        A[i][j]=int(st[j])
def Dijkstra(s):
    d=[10000]*10
    d[s]=0
    Q=set(range(10))
    V=set(range(10))
    while(len(Q)>0):
        u=list(Q)[0]
        for i in Q:
            if d[i]<d[u]:
                u=i
        Q-={u}
        for v in V-{u}:
            if (d[v]>d[u]+c[u][v]):
                d[v]=d[u]+c[u][v]
    return d[1]
result=0
DD=[0]*10
for i in range(10):
    DD[i]=Dijkstra(i)
for i in range(H):
    for j in range(W):
        if A[i][j]!=-1:
            result+=DD[A[i][j]]
print(result)

Solution (Python):

inp = []
inp.append(raw_input())
for i in xrange(10 + int(inp[0].split(" ")[0])):
    inp.append(raw_input())
Size = inp[0]

Mml = [None, 0] + [None] * 8
Cij = [[0] * 10 for i in range(10)]
for i in xrange(10):
    for j, a in enumerate(map(int,inp[i + 1].split(" "))):
        Cij[i][j] = a
        
    

def sloveMm(n):
    global Mml
    if(Mml[n] != None):
        return Mml[n]
    Nmm = Cij[n][1]
    rourt = [[n, 0, Nmm,n]]
    while len(rourt) > 0:
        rl = len(rourt)
        new_rourt = []
        for rn in xrange(rl):
            r = rourt[rn]
            for i in xrange(10):
                if i != r[0]:
                    nm = r[1] + Cij[r[0]][i]
                    if nm < Nmm:
                        """if Mml[i] != None:
                            Mml[n] = nm + Mml[i]
                            return nm + Mml[i]"""
                        if i == 1:
                            
                            Nmm = nm
                        new_rourt.append([i, nm, nm + Cij[i][1]] + r[3:] + [i] )
        rourt = new_rourt
    Mml[n] = Nmm
    return Nmm


NumberList = [0] * 10
for Ai in inp[11:]:
    
    for A in Ai.split(" "):
        if A != "-1" and A != "":
            NumberList[int(A)] += 1

ans = 0
for i, n in enumerate(NumberList):
    if n > 0:
        ans += sloveMm(i) * n
        


print ans

Solution (Python):
def main():
    h,w=[int(i) for i in input().split()]
    c=[]
    for i in range(10):
        c.append([int(i) for i in 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])
    ans=0
    for i in range(h):
        for j in [int(k) for k in input().split()]:
            if j!=1 and j!=-1:
                ans+=int(c[j][1])
    print(ans)

if __name__=='__main__':
    main()

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

    
def mini(S,dic,ans):
    if(S=={0,1,2,3,4,5,6,7,8,9}):
        return ans
    min_val=min(dic.values())
    for i in dic.keys():
        if dic[i]==min_val:
            S.add(i)
            pos=i
            break
    ans[pos]=dic.pop(pos)
    for i in dic.keys():
        dic[i]=min([dic[i],ans[pos]+C[i][pos]])
    return mini(S,dic,ans)

dic={}
for i in range(10):
    dic[i]=C[i][1]
M=mini(set(),dic,{})
M[-1]=0

ans=0
for i in range(H):
    for j in range(W):
        ans+=M[A[i][j]]
print(ans)

Solution (Python):

"""
https://beta.atcoder.jp/contests/abc079/tasks/abc079_d
AC
"""
import sys
from sys import stdin
input = stdin.readline


def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dp[i][k] + dp[k][j] < dp[i][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]


def main(args):
    H, W = map(int, input().split())
    dp = []
    for i in range(10):
        temp = [int(x) for x in input().split()]
        dp.append(temp)

    warshallFloyd(10, dp)

    costs = [dp[i][1] for i in range(10)]
    total_cost = 0
    for _ in range(H):
        for i in map(int, input().split()):
            if i != -1:
                total_cost += costs[i]
    print(total_cost)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):

"""
https://beta.atcoder.jp/contests/abc079/tasks/abc079_d

"""
import sys
from sys import stdin
input = stdin.readline


def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dp[i][k] + dp[k][j] < dp[i][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]


def main(args):
    H, W = map(int, input().split())
    dp = []
    for i in range(10):
        temp = [int(x) for x in input().split()]
        dp.append(temp)

    warshallFloyd(10, dp)

    costs = [dp[i][1] for i in range(10)]
    total_cost = 0
    for h in range(H):
        itr = map(int, input().split())
        for i in itr:
            if i != -1:
                total_cost += costs[i]
    print(total_cost)


if __name__ == '__main__':
    main(sys.argv[1:])

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)]
 
path = [[0]*10 for i in range(10)]
for i in range(10):
    for j in range(10):
        path[i][j] = c[i][j]
 
for k in range(10):
    for i in range(10):
        for j in range(10):
            path[i][j] = min(path[i][j], path[i][k]+path[k][j])
 
min_route = []
for i in range(10):
    min_route.append(path[i][1])
 
wall_num = [0]*10
for a in A:
    for i in range(10):
        wall_num[i] += a.count(i)
 
ans = 0
for i in range(10):
    ans += wall_num[i] * min_route[i]
 
print(ans)

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


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

warshall(10)

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

print(ans)

Solution (Python):
import numpy as np

N = 10
H, W = input().split()
H = int(H)
W = int(W)
C = np.zeros((N, N), dtype=np.int)
for i in range(N):
    line = input().split()
    C[i, :] = list(map(int, line))

A = np.zeros((H, W), dtype=np.int)
for h in range(H):
    w = input().split()
    A[h, :] = list(map(int, w))

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

s = 0
for a in A.reshape(-1):
    if a >= 0:
        s += C[a, 1]
print(s)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    h,w = LI()
    t = [LI() for _ in range(10)]
    a = [LI() for _ in range(h)]
    e = collections.defaultdict(list)
    for i in range(10):
        for j in range(10):
            e[i].append((j,t[j][i]))

    def search(s):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    d = search(1)
    r = 0
    for b in a:
        for c in b:
            if c*c == 1:
                continue
            r += d[c]

    return r



print(main())

Solution (Python):
def WF(lenV,E):
	D = E
	r = range(lenV)
	for k in r:
		for i in r:
			for j in r:
				D[i][j] = min(D[i][j], D[i][k]+D[k][j])
	return D
				
IN = input().split()
H = int(IN[0])
W = int(IN[1])
R = range(10)
E = [[float("inf") for i in R] for j in R]
for i in R:
	IN = input().split()
	for j in R:
		E[i][j] = int(IN[j])
D = WF(10,E)
C = [D[i][1] for i in R]
Ans = 0
for h in range(H):
	IN = input().split()
	for w in range(W):
		wall = int(IN[w])
		Ans += C[wall] if wall>=0 else 0
print(Ans)

Solution (Python):
import heapq


def func(start, mp):
    d = [float("inf") for i in xrange(10)]
    d[start] = 0
    q = [(0, start)]
    while len(q):
        c, n = heapq.heappop(q)
        if d[n] < c:
            continue
        for i in xrange(10):
            if d[i] > d[n]+mp[n][i]:
                d[i] = d[n]+mp[n][i]
                heapq.heappush(q, (d[i], i))
    return d[1]

h, w = map(int, raw_input().split())
mp = list()
for i in xrange(10):
    mp.append(map(int, raw_input().split()))

m = [func(i, mp) for i in xrange(10)]
print sum([sum(map(lambda x:m[x] if not x == -1 else 0, map(int, raw_input().split()))) for i in xrange(h)])

Solution (Python):

from collections import Counter
from heapq import heappush, heappop

def inpl(): return map(int, input().split())
H, W = inpl()
C = []
A = Counter()

for _ in range(10):
    C.append(tuple(inpl()))

for _ in range(H):
    A.update(tuple(inpl()))

min_cost = [float("inf") for _ in range(10)]

g = 1
for s in range(10):
    searched = [False] * 10
    searched[s] = True
    N = 10
    INF = float("inf")
    d = [INF for _ in range(N)]
    d[s] = 0
    heap = [[0, s]] 
    
    while len(heap):
        pcost, p = heappop(heap)
        searched[p] = True
        
        if d[p] < pcost:
            continue
        
        for i in range(10):
            if not searched[i]:
                new_cost = pcost + C[p][i]
                if new_cost < d[i]:
                    d[i] = new_cost
                    heappush(heap, [new_cost, i])
        
    min_cost[s] = d[1]

res = 0
for i in range(10):
    res += A[i] * min_cost[i]

print(res)

Solution (Python):
def cost(n,clist):
  for k in range(0,10):
    for i in range(0,10):
      for j in range(0,10):
        clist[i][j] = min(clist[i][j],clist[i][k]+clist[k][j])
  
  return clist[n][1]

def joisino(a,clist):
  note = [-1,0,-1,-1,-1,-1,-1,-1,-1,-1]
  answer = 0
  for raw in a:
    for number in raw:
      if number != -1:
        if note[number] == -1:
          note[number] = cost(number,clist)
        answer += note[number]
      
  return answer

def i_o():
  h, w = map(int,input().split(" "))
  i = 0 
  clist = []
  while i < 10:
    raw = list(map(int,input().split(" ")))
    clist.append(raw)
    i += 1
  a = []
  i = 1
  while i <= h:
    raw = list(map(int,input().split(" ")))
    a.append(raw)
    i += 1
  return h,w,clist,a

if __name__ == '__main__':
  h,w,clist,a = i_o()
  ans =joisino(a,clist)
  
  print(ans, flush=True)

Solution (Python):
def cost(n,clist):
  k = 0
  while k < 10:
    i = 0
    while i < 10:
      j = 0
      while j < 10:
        clist[i][j] = min(clist[i][j],clist[i][k]+clist[k][j])
        j += 1
      i += 1
    k += 1
  return clist[n][1]

def joisino(a,clist):
  note = [-1,0,-1,-1,-1,-1,-1,-1,-1,-1]
  answer = 0
  for raw in a:
    for number in raw:
      if number != -1:
        if note[number] == -1:
          note[number] = cost(number,clist)
        answer += note[number]
      
  return answer

def i_o():
  h, w = map(int,input().split(" "))
  i = 0 
  clist = []
  while i < 10:
    raw = list(map(int,input().split(" ")))
    clist.append(raw)
    i += 1
  a = []
  i = 1
  while i <= h:
    raw = list(map(int,input().split(" ")))
    a.append(raw)
    i += 1
  return h,w,clist,a

if __name__ == '__main__':
  h,w,clist,a = i_o()
  ans =joisino(a,clist)
  
  print(ans, flush=True)

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

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

cost = 0

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

for i in range(H):
	for j in range(W):
		if wall[i][j] != 1 and wall[i][j] != -1:
			cost += m[wall[i][j]][1]

print(cost)

Solution (Python):

import itertools

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 = sum([c[a][1] for a in itertools.chain.from_iterable(A) if a >= 0])
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] >= 0:
      ans += c[A[i][j]][1]
print(ans)

Solution (Python):


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

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

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

print(ans)

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

'''
def change(number):
    if number == -1:
        return 10
'''


a = []
for i in range(h):
    a.append(map(int, raw_input().split(" ")))

route = range(10)

def minroute(nowplace,d,passway,k):
    passp = passway[:]
    passp.append(nowplace)
    d1 = d + c[nowplace][1]
    for i in range(10):
        if (i in passp) or (c[nowplace][1] <= c[nowplace][i]): continue
        else:
            dk = minroute(i,d+c[nowplace][i],passp,k)
            if d1 > dk:
                d1 = dk
    return d1


for i in range(10):
    if i == 1:
        route[1] = 0
        continue
    route[i] = minroute(i,0,[1],i)

mp = 0
for l in a:
    for i in l:
        if i == -1:
            mp += 0
        else:
            mp += route[i]

print mp

Solution (Python):
def solve():
    H, W = list(map(int, input().split(" ")))
    d, A = [], []
    for _ in range(10):
        d.append(list(map(int, input().split(" "))))
    for _ in range(H):
        A += list(map(int, input().split(" ")))

    V, E = 10, 35
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

    sum = 0
    for a in A:
        if a == -1:
            pass
        else:
            sum += d[a][1]

    print(sum)
 

solve()

Solution (Python):

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

for i in range(10):
    for j in range(10):
        for k in range(10):
            if cost[j][k]>cost[j][i]+cost[i][k]:
                cost[j][k]=cost[j][i]+cost[i][k]
ans=0
for i in range(h):
    for j in map(int,input().split()):
        if j!=-1:
            ans+=cost[j][1]
print(ans)

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

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

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

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

print(ans)

Solution (Python):
def solve():
    H, W = list(map(int, input().split(" ")))
    d, A = [], []
    for _ in range(10):
        d.append(list(map(int, input().split(" "))))
    for _ in range(H):
        A += list(map(int, input().split(" ")))

    V, E = 10, 35
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

    sum = 0
    for a in A:
        if a == -1:
            pass
        else:
            sum += d[a][1]

    print(sum)
 

solve()

Solution (Python):
def rec_cost(x,acc,plist,clist):
  if x == 1:
    return acc
  else:
    minimum = -1
    for next in plist:
      nextplist = plist.copy()
      nextplist.remove(next)
      candidate = rec_cost(next,acc+clist[x][next],nextplist,clist)
      if minimum == -1:
        minimum = candidate
      elif candidate < minimum:
        minimum = candidate
    return minimum

def cost(n,clist):
  plist = [0,1,2,3,4,5,6,7,8,9]
  plist.remove(n)
  return rec_cost(n,0,plist,clist)

def joisino(a,clist):
  note = [-1,0,-1,-1,-1,-1,-1,-1,-1,-1]
  answer = 0
  for raw in a:
    for number in raw:
      if number != -1:
        if note[number] == -1:
          note[number] = cost(number,clist)
        answer += note[number]
      
  return answer

def i_o():
  h, w = map(int,input().split(" "))
  i = 0 
  clist = []
  while i < 10:
    raw = list(map(int,input().split(" ")))
    clist.append(raw)
    i += 1
  a = []
  i = 1
  while i <= h:
    raw = list(map(int,input().split(" ")))
    a.append(raw)
    i += 1
  return h,w,clist,a

if __name__ == '__main__':
  h,w,clist,a = i_o()
  ans =joisino(a,clist)
  
  print(ans, flush=True)