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



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

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

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

def min_cost(i,j,current,min_cost_current):
    if i == j: return current
    for index in range(10):
        if i == index: continue
        if current + mp[i][index] < min_cost_current:
            min_cost_current = min_cost(index,j,current+mp[i][index],min_cost_current)
    return min_cost_current


mp_min_cost =[]
for i in range(10):
    tmp = []
    for j in range(10):
        if i == j :
            tmp.append(0)
            continue

        min_cost_current = mp[i][j]
        if min_cost_current == sorted(mp[i])[1]:
            tmp.append(mp[i][j])
            continue

        
        for index in range(10):
            if i == index: continue
            if mp[i][index] < min_cost_current:
                min_cost_current = min_cost(index,j,mp[i][index],min_cost_current)
        tmp.append(min_cost_current)
    mp_min_cost.append(tmp)

amount = 0
for i in wall:
    for j in i:
        if j == -1 or j == 1: continue
        amount += mp_min_cost[j][1]
print(amount)

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

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

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

    for k in range(C):
        for i in range(C):
            for j in range(C):
                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)

if __name__ == '__main__':
    main()

Solution (Python):
def d_wall(H, W, C, A):
    cost=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])
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] != -1:
                ans += cost[A[i][j]][1]
    return ans

H,W = [int(i) for i in input().split()]
C = [[int(i) for i in input().split()] for j in range(10)]
A = [[int(i) for i in input().split()] for j in range(H)]
print(d_wall(H, W, C, A))

Solution (Python):

H, W = map(int, raw_input().split())
c = [[0 for i in range(10)] for j in range(10)]
A = [[0 for i in range(W)] for j in range(H)]
for i in range(10):
    n = map(int, raw_input().split())
    for j in range(10):
        c[i][j] = n[j]
for i in range(H):
    n = map(int, raw_input().split())
    for j in range(W):
        A[i][j] = n[j]
        
def getDistance(start):
    if start == 1:
        return 0
    d = [1001 for i in range(10)]
    d[start] = 0
    prev = [-1 for i in range(10)]
    Q = set()
    for i in range(10):
        Q.add(i)
    while len(Q) != 0:
        min = 1001
        for i in range(10):
            if d[i] < min and i in Q:
                min = d[i]
                u = i
        Q.remove(u)
        for v in range(10):
            if d[v] > d[u] + c[u][v]:
                d[v] = d[u] + c[u][v]
                prev[v] = u
    return(d[1])



if __name__ == '__main__':
    D = [0 for i in range(10)]
    for i in range(10):
        D[i] = getDistance(i)
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] != -1:
                ans += D[A[i][j]]
    print(ans)

Solution (Python):
H, W = list(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)]

flag = True
while flag:
    flag = False
    for i in range(10):
        for j in range(10):
            for k in range(10):
                if c[i][k] + c[k][j] < c[i][j]:
                    c[i][j] = c[i][k] + c[k][j]
                    flag = True

result = 0
countNumber = []
for i in range(10):
    if i != 1:
        a = sum([A[h].count(i) for h in range(H) if i in A[h]])
        countNumber.append(a)
        if countNumber[-1] != 0:
            result += c[i][1] * countNumber[-1]
print(result)

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

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

def mincost(start,goal):
    queue = []
    queue.append((start,[],0))
    queue[0][1].append(start)
    mincost = 99999999999999999999999999999
    while len(queue) != 0:
        q = queue.pop(0)
        if q[0] == goal:
            if q[2] < mincost:
                mincost = q[2]
        else:
            for i in range(10):
                if i not in q[1]:
                    tq = q[1].copy()
                    tq.append(i)
                    if q[2]+MP[q[0]][i] < mincost:
                        queue.append((i,tq,q[2]+MP[q[0]][i]))
    return mincost

need_magical_power = 0
mincost_list = []
for i in range(10):
    mincost_list.append(mincost(i,1))


for h in range(H):
    for w in range(W):
        if board[h][w] == -1 or board[h][w] == 1:
            pass
        else:
            need_magical_power += mincost_list[board[h][w]]

print(need_magical_power)

Solution (Python):
from collections import deque
h, w = [int(x) for x in raw_input().split()]
c = [[int(x) for x in raw_input().split()] for line in xrange(10)]
a = [[int(x) for x in raw_input().split()] for line in xrange(h)]
for t in xrange(10):
    for i in xrange(10):
        for j in xrange(10):
            for k in xrange(10):
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])
cost = 0
for line in xrange(h):
    for col in xrange(w):
        if a[line][col] in [-1, 1]:
            continue
        else:
            cost += c[a[line][col]][1]
print cost

Solution (Python):
table = {1: 0}

def solve():
    global c, table
    queue = []
    for i in range(10):
        if i == 1:
            continue
        queue.append((c[i][1], i))
    while queue:
        queue.sort(reverse=True)
        a = queue.pop()
        if a[1] not in table:
            table[a[1]] = a[0]
            for i in range(10):
                if i == a[1]:
                    continue
                queue.append((a[0]+c[i][a[1]], i))

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

solve()

ans = 0
for i in range(H):
    for j in range(W):
        if 0 <= A[i][j] <= 9:
            ans += table[A[i][j]]

print(ans)

Solution (Python):
import copy
import sys
import numpy as np
import heapq
import time

from math import *
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

class warshall_floyd:
    def __init__(self):
        self.A = []

    def execute(self, adj_mat):
        self.A = copy.deepcopy(adj_mat)
        for k in range(len(self.A)):
            for i in range(len(self.A)):
                if self.A[i][k] < sys.maxint:
                    for j in range(len(self.A)):
                        if self.A[k][j] < sys.maxint:
                            self.A[i][j] = min(self.A[i][j], self.A[i][k] + self.A[k][j])


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W] = [int(input_raw[0]), int(input_raw[1])]
    dist_mat = [[0 for i in range(10)] for j in range(10)]
    for i in range(10):
        input_raw = read_func().strip().split()
        cost_list = (list(input_raw))
        for j in range(10):
            dist_mat[i][j] = int(cost_list[j])

    Warshall = warshall_floyd()
    Warshall.execute(dist_mat)

    score = 0;
    for i in range(H):
        input_raw = read_func().strip().split()
        raw_list = list(input_raw)
        for j in range(W):
            num = int(raw_list[j])
            if num >= 0:
                score += Warshall.A[num][1]

    print score;

if __name__ == '__main__':
    main()

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

for i in range(10):
    c_new = [[None for x in range(10)] for y in range(10)]
    for j in range(10):
        for k in range(10):
            c_new[j][k] = min(c[j][k], c[j][i] + c[i][k])
    c = copy.copy(c_new)

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

Solution (Python):
from scipy.sparse.csgraph import dijkstra

H, W = map(int,input().split())
c = [[0 for i in range(10)] for j in range(10)]
for i in range(10):
    c[i] = list(map(int, input().split()))
t = dijkstra(c)
ans = 0
for i in range(H):
    for k in map(int, input().split()):
        if k == 1 or k == -1: continue
        ans += t[k][1]
print(int(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)]

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


from sys import stdin

def warshallfloyd(d):
  n = len(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])

def solve(c, A):
  warshallfloyd(c)
  cost = 0
  for i in range(len(A)):
    for j in range(len(A[i])):
      if A[i][j] >= 0:
        cost += c[A[i][j]][1]
  return cost

def readints():
  return map(int, stdin.readline().split())

H, W = readints()
c = []
for i in range(10):
  c.append(readints())
A = []
for i in range(H):
  A.append(readints())
print(solve(c, A))

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

C = []
costs = {}
for i in range(10):
  C.append(list(map(int, input().split())))
  costs[i] = [float('inf')]*10
  costs[i][i] = 0
costs[-1] = [0]*10

for i in range(10):
  end = set()
  q = []
  heapq.heappush(q, (0, i))
  while len(q):
    c, k = heapq.heappop(q)
    if k == 1:
      break
    if costs[i][k] < c:
      continue
    end.add(k)
    for j in range(10):
      if j not in end:
        costs[i][j] = min(costs[i][j], c+C[k][j])
        heapq.heappush(q, (costs[i][j], j))

ans = 0
for i in range(H):
  ans += sum(map(lambda x: costs[int(x)][1], input().split()))

print(ans)

Solution (Python):



import numpy as np

hw = raw_input()
hw = hw.split()
h,w = map(int,hw)

c = np.zeros([10,10],int)
for i in range(10):
    line = raw_input()
    line = line.split()
    c[i] = map(int,line)







suji_num = np.zeros([10],int)
for i in range(h):
    line = raw_input()
    line = line.split()
    line = map(int,line)
    for j in range(10):
        num = line.count(j)
        suji_num[j] += num

maryoku = np.zeros([10],int)

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

i = 1
while i < max(maryoku):
    
    for j in range(10):
        if maryoku[j] == i:
            for k in range(10):
                keiyum = c[k,j]+i
                if keiyum < maryoku[k]:
                    maryoku[k] = keiyum
    i += 1

ans = 0
for i in range(10):
    ans += suji_num[i] * maryoku[i]

print ans

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

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

A = [[0]*W for i in range(H)]

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

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

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

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

if __name__ == '__main__':
    main()

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

A = [[0]*W for i in range(H)]

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

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

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

Solution (Python):
import copy

h,w = map(int, raw_input().split(" "))

c = []

def search(num,c,prev,now,nopath):
  if num == 1:
    return now
  mindata = prev + c[num][1]
  for a in range(10):
    if a==1:continue
    if a in nopath:
      continue
    if (prev + c[num][a]) < mindata:
      np2 = copy.deepcopy(nopath)
      np2.append(a)
      q = search(a,c,prev + c[num][a],prev + c[num][1],np2)
      if q < mindata:
        mindata = q
  if mindata < now:
    return mindata
  else:
    return now

for a in range(0,10):
  c.append(map(int, raw_input().split(" ")))

wall = ""

for a in range(h):
  q = raw_input().split(" ")
  for x in q:
    if x != "-1":
      wall += x




num = [0]*10
for a in range(10):
  if str(a) in wall:
    num[a] = -1



for a in range(10):
  if a == 1:
    num[a] = 0
  if num[a] == -1:
    q = [a]
    num[a] = search(a,c,0,c[a][1],q)
  else:
    continue

ans = 0
for a in wall:
  ans += num[ int(a) ]
print ans

Solution (Python):


def f(C):
    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]

    return C


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

    f(C)

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

    res = 0

    for a in A:
        for i in a:
            if i < 0:
                continue
            res += C[i][1]

    print(res)
    return 0

if __name__ == '__main__':
    main()

Solution (Python):
H, W = map(int, input().split())
c = []
w = []
for i in range(10):
    c.append(list(map(int, input().split())))
for i in range(H):
    w.append(list(map(int, input().split())))
for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j] = min(c[i][j], c[i][k] + c[k][j])
p = 0
for r in w:
    for n in r:
        if n == -1:
            pass
        else:
            p += c[n][1]
print(p)

Solution (Python):
import heapq

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

N = 10
adj = [[] for i in range(N)]
for i in range(N):
    for j in range(N):
        adj[j].append((i, cs[i][j]))


cost = [float('inf') for i in range(N)]
cost[1] = 0

pq = []
heapq.heappush(pq, (0, 1))

while pq:
    c, vNow = heapq.heappop(pq)
    if c > cost[vNow]: continue

    for v2, w in adj[vNow]:
        if cost[vNow] + w < cost[v2]:
            cost[v2] = cost[vNow] + w
            heapq.heappush(pq, (cost[v2], v2))


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

print(ans)

Solution (Python):
import heapq

def dijkstra(N,start, goal, E):
    """最短距離,経路を返すプログラム"""
    dist = [float('inf')] * N          
    path = [tuple() for n in range(N)] 
    dist[start] = 0
    path[start] = (start, )            
    pq = [(0, path[start])]

    while pq:
        di, pathi = heapq.heappop(pq)
        v = pathi[-1]

        if v == goal:
            return di

        
        for vertex, weight in E[v].items():
            new_di = di + weight
            if (new_di < dist[vertex]) or (new_di == dist[vertex] and pathi + (vertex, ) < path[vertex]):
                dist[vertex] = new_di
                path[vertex] = pathi + (vertex, )
                heapq.heappush(pq, (new_di, path[vertex]))



N = 10
H,W = map(int, input().split())
E = [dict() for i in range(10)]
ans = 0

tank = [0] * 10
for i in range(10):
    tmp = list(map(int,input().split(" ")))
    for j in range(10):
        E[i][j] = tmp[j]

for i in range(H):
    A = list(map(int,input().split(" ")))
    for j in range(W):
        if abs(A[j]) != 1:
            if tank[A[j]] == 0: 
                tank[A[j]] = dijkstra(N,A[j],1,E)

            ans += tank[A[j]]

print(ans)

Solution (Python):

import numpy as np
from collections import Counter

h, w = list(map(int,input().split()))
graph = np.zeros((10,10)).astype('int32')
a = np.zeros((h,w)).astype('int32')
for i in range(10):
    graph[i] = list(map(int,input().split()))
for i in range(h):
    a[i] = list(map(int,input().split()))

e, v = 90, 10
path = np.zeros((v,v)).astype('uint32')

for i in range(v):
    for j in range(v):
            path[i][j] = j
            
for k in range(v):
    for i in range(v):
        for j in range(v):
            if(graph[i][k]+graph[k][j]<graph[i][j]):
                graph[i][j] = graph[i][k]+graph[k][j]
                path[i][j] = path[i][k]
                
            
apy = a.ravel().tolist()
cnt = Counter(apy)
ans = 0
for i in range(10):
    ans += cnt[i]*graph[i][1]
print(ans)

Solution (Python):
from collections import Counter,defaultdict
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)]


cost = dict()


d = Counter()

for a in A:
    for i in a:
        if i==-1 or i==1:
            continue
        else:
            d[i]+=1




def search(glaph, start, goal):
    def get_path(start, goal, prev):
        path = []
        now = goal
        path.append(now)
        while True:
            path.append(prev[now])
            if prev[now] == start: break
            now = prev[now]
        path.reverse()
        return path

    MAX_VAL = 0x10000000
    g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    return [get_path(start, goal, prev), cost[goal]]
ans = 0
for key in d:
    ans += d[key]*search(C,key,1)[1]
print(ans)

Solution (Python):



import itertools

rows_nr, cols_nr = (int(x) for x in input().split())
d1___d2___cost = []
for i in range(10):
    d1___d2___cost_i___j = [int(x) for x in input().split()]
    d1___d2___cost.append(d1___d2___cost_i___j)
r_c___value = []
for row in range(rows_nr):
    c___value = [int(x) for x in input().split()]
    r_c___value.append(c___value)

f = d1___d2___cost
for i, v, u in itertools.product(range(10), repeat=3):
    f[u][v] = min(f[u][v], f[u][i] + f[i][v])
ans = 0
for row in r_c___value:
    for value in row:
        if value == -1:
            continue
        ans += f[value][1]
print(ans)

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

o = [c[n][1] for n in range(10)]

for _ in range(10):
    for i in range(10):
        for t in range(10):
            o[i] = min(o[i], c[i][t] + o[t])

print(sum([o[a] for a in A if a >= 0]))

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

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

ans = 0
for i in range(h):
    v = map(int, input().split())
    for x in v :
        if x >= 0 : ans += d[x][1]

print(ans)

Solution (Python):
from collections import Counter,defaultdict
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)]


cost = dict()


d = Counter()

for a in A:
    for i in a:
        if i==-1 or i==1:
            continue
        else:
            d[i]+=1

def get_path(start, goal, prev):
    path = []
    now = goal
    path.append(now)
    while True:
        path.append(prev[now])
        if prev[now] == start: break
        now = prev[now]
    path.reverse()
    return path

def search(glaph, start, goal):
    MAX_VAL = 0x10000000
    g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    return [get_path(start, goal, prev), cost[goal]]
ans = 0
for key in d:
    ans += d[key]*search(C,key,1)[1]
print(ans)

Solution (Python):


import itertools

NUM_TYPES = 10
INVALID = -1


def in_place_min_costs(min_dist, num_vs=NUM_TYPES):
    for k, i, j in itertools.product(range(num_vs), repeat=3):
        min_dist[i][j] = min(min_dist[i][j], min_dist[i][k] + min_dist[k][j])


def solve(h, w, cs, board):
    in_place_min_costs(cs)
    res = 0
    for i, j in itertools.product(range(h), range(w)):
        b = board[i][j]
        if b != INVALID:
            res += cs[b][1]
    return res


def main():
    h, w = (int(x) for x in input().split())
    cs = [[int(x) for x in input().split()] for _ in range(NUM_TYPES)]
    board = [[int(x) for x in input().split()] for _ in range(h)]
    res = solve(h, w, cs, board)
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):

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

count_ = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for _ in range(H):
    for w in map(int, input().split()):
        if w >= 0:
            count_[w] += 1


DP = [1000]*10
DP[1] = 0

end = 0
while end == 0:
    end = 1
    for i in range(10):
        a = min([C[i][j] + DP[j] for j in range(10)])
        if a < DP[i]:
            end = 0
            DP[i] = a
            
print(sum([DP[j]*count_[j] for j in range(10)]))

Solution (Python):
h,w = map(int,raw_input().split())
c = []
dist = []
for i in xrange(10):
    c.append(map(int,raw_input().split()))
    dist.append([100000000]*10)
a = []
for i in xrange(h):
    a.append(map(int,raw_input().split()))

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

cost = 0
for i in xrange(h):
    for j in xrange(w):
        if a[i][j] != -1:
            cost += dist[a[i][j]][1]
print cost

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 _ in range(100):
    for u in range(10):
        for v in range(10):
            for w in range(10):
                c[u][w] = min(c[u][w], c[u][v] + c[v][w])

ans = 0
for ai in a:
    for aij in ai:
        if abs(aij) != 1:
            ans += c[aij][1]
print(ans)

Solution (Python):
h, w = map(int, input().split())
costs = [list(map(int, input().split())) 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 _ in range(h):
    for n in map(int, input().split()):
        if n == -1:
            continue
        ans += costs[n][1]

print(ans)

Solution (Python):
h, w = map(int, input().split())
c = []
for i in range(10):
    c.append(list(map(int, input().split())))
for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j] = min(c[i][j], c[i][k] + c[k][j])
ans = 0
for j in range(h):
    a = list(map(int, input().split()))
    for j in range(w):
        if a[j] != -1:
            ans += c[a[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 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])
print sum(sum(c[a][1] if a>=0 else 0 for a in aa) for aa in A)

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

Solution (Python):
n, m = map(int, raw_input().split())

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

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

s = 0
for i in range(n):
	for x in map(int, raw_input().split()):
		if x != -1:
			s += a[x][1]
print s

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

h, w = na()
g = []
for i in range(10):
    g.append(na())

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

ret = 0
for i in range(h):
    row = na()
    for v in row:
       if v >= 0:
           ret += g[v][1]
print(ret)

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])
print(sum([sum(map(lambda a: 0 if a == -1 else C[a][1], row)) for row in A]))

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