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, *ca = map(int, open(0).read().split())
    it = zip(*[iter(ca[:100])] * 10)
    *c, = map(lambda i: list(i), it)
    a = ca[100:]

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

    ans = 0
    cost = {i: c[i][1] for i in [0, 2, 3, 4, 5, 6, 7, 8, 9]}

    for i in a:
        if i in [-1, 1]:
            continue
        ans += cost[i]

    print(ans)


if __name__ == '__main__':
    main()

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

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

    ans = 0

    for i in a:
        if i in [-1, 1]:
            continue
        ans += c[i][1]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
h, w = map(int, input().split())
C = [tuple(map(int, input().split())) for _ in range(10)]
A = [tuple(map(int, input().split())) for _ in range(h)]
AtoOne = [1001 for i in range(10)]

from collections import deque
q = deque([[1, 0]])

while q:
    i, cost = q.popleft()
    if AtoOne[i] > cost:
        AtoOne[i] = cost
    else:
        continue

    for j in range(10):
        if i == j:
            continue
        q.append([j, cost + C[j][i]])

counts = [0] * 10
for i in range(h):
    for j in range(w):
        a = A[i][j]
        if a > -1:
            counts[a] += 1
ans = 0 
for from_i, c in enumerate(counts):
    ans += c * AtoOne[from_i]
print(ans)

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

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

def main(args):
    H,W = map(int,input().split())
    cost = [[0] for _ in range(10)]
    for i in range(10):
        cost[i] = list(map(int,input().split()))
    
    wall = [[] for _ in range(H)]
    for i in range(H):
        wall[i] = list(map(int,input().split()))
    
    warshallFloyd(10, cost)
    
    cost_to_one = [0]*10
    for i in range(10):
        cost_to_one[i] = cost[i][1]
    
    
      
    ans = 0
    for i in range(H):
        for j in range(W):
            if wall[i][j] != -1:
                ans += cost_to_one[wall[i][j]]
    
    print(ans)
    
if __name__ == '__main__':
    main(sys.argv[1:])

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

def warshall_floyd(d, n):
    
    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
dist = warshall_floyd(c,10)
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == -1:
            continue
        ans += dist[a[i][j]][1]
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

h,w=mii()

mat=[limii() for _ in range(10)]

arr=[limii() for _ in range(h)]

chk=shortest_path(csr_matrix(mat))

ans=0

for i in arr:
    for j in i:
        if j!=-1:
            ans+=int(chk[j][1])
print(ans)

Solution (Python):
def warshall_floyd(graph):
    
    n_nodes = len(graph)

    froms = []
    
    for i in range(len(graph)):
        froms.append([])
        for j in range(len(graph[i])):
            if i == j:                          
                froms[i].append(0)
            elif graph[i][j] < float("inf"):    
                froms[i].append(i)
            else:
                froms[i].append(None)

    
    for k in range(n_nodes):
        for i in range(n_nodes):
            for j in range(n_nodes):
                adj_cost = graph[i][k] + graph[k][j]
                if adj_cost < graph[i][j]:
                    
                    
                    graph[i][j] = adj_cost
                    froms[i][j] = froms[k][j]
    
    has_negative_loop = False
    for i in range(n_nodes):
        if graph[i][i] < 0:
            has_negative_loop = True
            break

    return graph, froms, has_negative_loop


def resolve():
    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)]
    C, _, __ = warshall_floyd(C)
    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)

        

if '__main__' == __name__:
    resolve()

Solution (Python):
def solve(hajime, ima, wa):
  for i in range(10):
    
    
    
    if i == 1 and wa + c[ima][i] < toone[hajime]:
      toone[hajime] = wa + c[ima][i]
    elif wa + c[ima][i] < toone[hajime] and i != ima:
      solve(hajime, i, wa+c[ima][i])
  return
      
    


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)]
toone=[10**4]*10
toone[1]=0

for i in range(10):
  if i != 1:
    solve(i, i, 0)


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

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

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

spell=0
for wist in a:
  for val in wist:
    if val==-1:continue
    spell+=c[val][1]
print(spell)

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


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

cost = warshall_floyd(c)

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

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

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

ans = 0
for _ in range(H):
    for x in map(int, input().split()):
        if x >= 0:
            ans += cost[x][1]
print(ans)

Solution (Python):
def wa(l):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                l[i][j] = min(l[i][j], l[i][k] + l[k][j])
    return l
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)]
l = wa(c)
ans = 0
for i in a:
    for j in i:
        if j != -1:
            ans += l[j][1]
print(ans)

Solution (Python):
def main():
    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
    def flatten_list(l):
        for el in l:
            if isinstance(el, list):
                yield from flatten_list(el)
            else:
                yield el
    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)]
    A = list(flatten_list(A))
    C = warshall_floyd(C)
    ans = 0
    for a in A:
        if a != -1:
            ans += C[a][1]
    print(ans)


if __name__ == '__main__':
    main()

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

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

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


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

Solution (Python):
import copy

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

INF = 10 ** 6
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])

res = 0
for arr in A:
    for a in arr:
        if a == -1:
            continue
        else:
            res += d[a][1]

print(res)

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

INF = 10 ** 6
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])

res = 0
for arr in A:
    for a in arr:
        if a == -1:
            continue
        else:
            res += c[a][1]

print(res)

Solution (Python):



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

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

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

ans = 0
for i in num:
    for j in i:
        if j == 1 or j == -1:
            continue
        else:
            ans += edge[j][1]

print(ans)

Solution (Python):



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

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

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

ans = 0
for i in num:
    for j in i:
        if j == 1 or j == -1:
            continue
        else:
            ans += edge[j][1]

print(ans)

Solution (Python):
H, W = 2, 4
ARR = [
    [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]
]

CRR = [
    [-1, -1, -1, -1],
    [8, 1, 1, 8],
]


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

ARR = []

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

CRR = []

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


def calculate(h, w, arr, crr):
    for i in range(0, 10):
        for j in range(0, 10):
            for k in range(0, 10):
                s1 = arr[j][i] + arr[i][k]
                s2 = arr[j][k]
                arr[j][k] = min(s1, s2)

    result = 0
    for cr in crr:
        for c in cr:
            if c == -1:
                continue
            else:
                result += arr[c][1]

    print(result)


calculate(H, W, ARR, CRR)

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])
d = {i: 0 for i in range(-1, 10)}
for _ in range(H):
    A = map(int, input().split())
    for i in A:
        d[i] += 1
ans = 0
for i in range(10):
    if i == 1:
        continue
    ans += c[i][1] * d[i]
print(ans)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    H, W = map(int, readline().split())
    C = [list(map(int, readline().split())) for _ in range(10)]
    A = list(map(int, read().split()))

    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 n in A:
        if n != -1:
            ans += C[n][1]

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    H, W = map(int, readline().split())
    C = [list(map(int, readline().split())) for _ in range(10)]
    A = list(map(int, read().split()))

    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 n in A:
        if n != -1:
            ans += C[n][1]

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    H, W = map(int, readline().split())
    C = [list(map(int, readline().split())) for _ in range(10)]
    A = list(map(int, read().split()))

    counter = Counter(A)

    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 n, freq in counter.items():
        if n not in (-1, 1):
            ans += C[n][1] * freq

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys


from collections import deque, Counter, defaultdict


import heapq
import time

start = time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

h,w = rl()
c=[rl() 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):
    a=rl()
    for num in a:
        if num==-1:
            continue
        ans+=c[num][1]
print(ans)

Solution (Python):
class WarshallFloyd:
    
    def __init__(self,n,_first_index=0):
        self.v = n
        self._first_idx=_first_index
        self.d = [[float("INF")]*(n) for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        f=self._first_idx
        self.d[x-f][y-f] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        return self.d
h,w=map(int,input().split())
war=WarshallFloyd(10)
for i in range(10):
    s=list(map(int,input().split()))

    for j in range(10):
        war.path(i,j,s[j])
dis=war.build()
from collections import Counter as co
l=[list(map(int,input().split())) for i in range(h)]
l=sum(l,[])
var=co(l).items()
print(sum([0]+[v*dis[k][1] for k,v in var if k!=-1]))

Solution (Python):
import sys
import math
from collections import deque
from itertools import permutations

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    H, W = NMI()
    C = [NLI() for _ in range(10)]
    A = [NLI() for _ in range(H)]

    for i in range(10):
        for perm in permutations("0123456789", 3):
            now = int(perm[0])
            cost = 0
            for p in perm[1:]:
                p = int(p)
                cost += C[now][p]
                now = p
            C[int(perm[0])][now] = min(C[int(perm[0])][now], cost)

    ans = 0
    for h in range(H):
        for w in range(W):
            now = A[h][w]
            if now == -1: continue
            ans += C[now][1]
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def warshall_floyd(v_count: int, matrix: list) -> list:
    """ ワーシャルフロイド
    v_count: 頂点数
    matrix: 隣接行列(到達不能はfloat("inf"))
    """
    for i in range(v_count):
        for j, c2 in enumerate(row[i] for row in matrix):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix


h, w = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
warshall_floyd(10, c)
ans = 0
for _ in range(h):
    for x in list(map(int, input().split())):
        if x >= 0:
            ans += c[x][1]
print(ans)

Solution (Python):
import sys
import collections

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


def main():
    H, W = map(int, readline().split())
    c = []
    for _ in range(10):
        c.append(list(map(int, readline().split())))
    wall = []
    wallcount = collections.Counter([])
    for _ in range(H):
        tmp = list(map(int, input().split()))
        wall.append(tmp)
        wallcount += collections.Counter(tmp)
    wallitem = list(zip(*wallcount.items()))
    
    for k in range(10):
        for i in range(10):
            for j in range(10):
                c[i][j] = min(c[i][k] + c[k][j], c[i][j])
    
    ans = 0
    for item in wallitem[0]:
        if item in [-1, 1]:
            continue
        ans += wallcount[item]*c[item][1]

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import collections

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

def dfs(n, used, cost):
    global c, mincost
    for i in range(10):
        if i == 1:
            if cost + c[n][i] < mincost:
                mincost = cost + c[n][i]
                continue
        if i not in used and cost < mincost:
            dfs(i, used+[i], cost+c[n][i])

def main():
    global c, mincost
    H, W = map(int, readline().split())
    c = []
    for _ in range(10):
        c.append(list(map(int, readline().split())))
    wall = []
    wallcount = collections.Counter([])
    for _ in range(H):
        tmp = list(map(int, input().split()))
        wall.append(tmp)
        wallcount += collections.Counter(tmp)
    
    wallitem = list(zip(*wallcount.items()))
    ans = 0
    for i, item in enumerate(wallitem[0]):
        if item in [-1, 1]:
            continue
        mincost = c[item][1]
        dfs(item, [item], 0)
        ans += mincost*wallitem[1][i]
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def warshall_floyd(d,n):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

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

num_cnt = [0]*10
for _ in range(h):
    al = list(map(int, input().split()))
    for a in al:
        if a >= 0: num_cnt[a] += 1

warshall_floyd(c,10)

ans = 0
for num, cnt in enumerate(num_cnt):
    ans += c[num][1] * cnt

print(ans)

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

a=[[0]*w for _ in range(h)]
for i in range(h):
    a[i]=list(map(int, input().split()))


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


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

Solution (Python):
import copy

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


while True:
    prev = copy.deepcopy(dp)
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if i == j:
                    continue
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    if prev == dp:
        break
    prev = dp

ans = 0
for i in range(h):
    arr = list(map(int, input().split()))
    ans += sum([dp[x][1] for x in arr if x != -1])

print(ans)

Solution (Python):
def warshall_floyd(d):
    global n
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

h,w = map(int,input().split())
n = 10
d = [[] for i in range(10)]
for i in range(10):
    for j in map(int,input().split()):
        d[i].append(j)
D = warshall_floyd(d)
ans = 0
for i in range(h):
    for j in map(int,input().split()):
        if j != -1:
            ans += D[j][1]
print(ans)

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

for i in range(10):
    costtoone.append(maptrans[i][1])

for loop in range(10): 
    for tonum in range(10): 
        for i in range(10):
            costtoone[i] = min(costtoone[i], costtoone[tonum] + maptrans[i][tonum])




maze = []
for hh in range(h):
    l = list(map(int, input().split()))
    maze.append(l)

res = 0
for hh in range(h):
    for ww in range(w):
        if maze[hh][ww] == 1 or maze[hh][ww] == -1:
            continue
        
        res += costtoone[maze[hh][ww]]
print(res)

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

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

"""
各数字から各数字への変更コストの最小値をわーシャルフロイドで計算する
"""

for i in range(10):
    for j in range(10):
        for k in range(9,-1,-1):
            dp[j][k] = min(dp[j][k],dp[j][i]+dp[i][k])

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

print(cost)

Solution (Python):
from itertools import permutations
from collections import Counter

def main():
    H, W = map(int, input().split())
    cost = [[0]*10 for _ in range(10)]

    for i in range(10):
        line = tuple(map(int, input().split()))
        for j, e in enumerate(line):
            cost[i][j] = e

    seq = (0, 2, 3, 4, 5, 6, 7, 8, 9)
    for i in range(2, 10):
        for p in permutations(seq, i):
            temp = sum([cost[p[j]][p[j+1]] for j in range(i-1)])
            temp += cost[p[-1]][1]
            cost[p[0]][1] = min(cost[p[0]][1], temp)

    c = Counter()
    for _ in range(H):
        temp = Counter(tuple(map(int, input().split())))
        c += temp

    ans = 0
    for i in seq:
        ans += c[i] * cost[i][1]
    print(ans)

if __name__ == "__main__":
    main()

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

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



cost = warshall_floyd(C)

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

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

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

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)]
mn = [[int(1e9) for j in range(10)] for i in range(10)]

def dfs(s, n, d):
    if n == 1:
        mn[s][n] = min(mn[s][n], d)
    else:
        if mn[s][n] <= d:
            return
        mn[s][n] = min(mn[s][n], d)
        for i in range(10):
            dfs(s, i, d+c[n][i])


for i in range(10):
    dfs(i, i, 0)

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

print(ans)

Solution (Python):
from itertools import product
import numpy as np

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

INF = 10 ** 9

dp = np.ones(shape=(10, 10), dtype=int) * INF

for i in range(10):
    costs = tuple(map(int, input().split(' ')))
    for j in range(10):
        dp[i][j] = costs[j]

for k, i in product(range(10), repeat=2):
    dp[i] = np.minimum(dp[i], dp[i][k] + dp[k])

cost = 0
for _ in range(H):
    numbers = tuple(map(int, input().split(' ')))
    for n in numbers:
        if n < 0:
            continue
        cost += dp[n][1]

print(cost)

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

from collections import defaultdict

V = defaultdict(list)
 
for x in range(10):
    al = ab[x]
    for y in range(10):
        V[x].append([y,al[y]])

def dfs(source):
    dist = [99]*10
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        for b in V[a]:
            if dist[b[0]]!=99:
                if dist[b[0]] > dist[a]+b[1]:
                    q.append(b[0])
                dist[b[0]] = min(dist[b[0]],dist[a]+b[1])
                continue
            dist[b[0]] = dist[a] + b[1]
            q.append(b[0])
    return dist

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

import itertools
ss = list(itertools.chain.from_iterable(hw))

import collections
c = collections.Counter(ss)

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

print(res)

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

for i in maze:
    for j in i:
        if j != -1:
            ans += c[j][1]

print(ans)

Solution (Python):
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
import itertools
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


n=10
h,w=mp()
d=[lmp() for i in range(n)]
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])
ans=0
for i in range(h):
    l=lmp()
    for k in range(w):
        if l[k]!=-1:
            ans+=d[l[k]][1]
print(ans)

Solution (Python):
import copy
h,w = map(int,input().split())
c = [list(map(int,input().split())) for i in range(10)]
G = [list(map(int,input().split())) for i in range(h)]
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 G[i][j] != -1:
      ans += d[G[i][j]][1]
      
print(ans)