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 8s, 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



Sample input:
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:
12

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

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)

Submission status: Accepted

Solution code:
def warshall_floyd(graph):
    # 頂点数
    n_nodes = len(graph)

    froms = []
    # 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"):    # i -> j間に辺がある場合、ひとまずiをdestに行く直前のnodeとしておく
                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]:
                    # i -> jの最短経路は i -> k -> jであることを意味する
                    # よってjの直前に立ち寄る頂点は k -> j の最短経路において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()

Submission status: Accepted

Solution code:
def solve(hajime, ima, wa):
  for i in range(10):
    #print("hajime : "+str(hajime))
    #print("ima : "+str(ima))
    #print("wa : " + str(wa))
    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)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def warshall_floyd(c):
    #d[i][j]: iから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])
    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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):
    #d[i][j]: iからjへの最短距離
    for k in range(10):
        for i in range(10):
            for j in range(10):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc079/tasks/abc079_d
# ワーシャルフロイド

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):
            # iからjへの最短距離
            # 負の辺がある場合　つっこむとかなり遅くなる
            # if edge[i][k] != float('inf') and edge[k][j] != float('inf'):
            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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
#import time
#import copy
from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
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)]
#g=[[inf]*h 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 _ in range(h):
    a=rl()
    for num in a:
        if num==-1:
            continue
        ans+=c[num][1]
print(ans)

Submission status: Accepted

Solution code:
class WarshallFloyd:
    #O(V^3)で任意２頂点の最短距離
    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]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def warshall_floyd(d,n):
    #d[i][j]: iからjへの最短距離
    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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
maptrans = []
for i in range(10):
    l = list(map(int, input().split()))
    maptrans.append(l)
costtoone = []
# ダイレクトに1に行くときのコスト
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])

#print(costtoone)


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
        #print(maze[hh][ww], "=" ,costtoone[maze[hh][ww]])
        res += costtoone[maze[hh][ww]]
print(res)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):
    #d[i][j]: iからjへの最短距離
    for k in range(10):
        for i in range(10):
            for j in range(10):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

##############################

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
#print(num)
ans = 0
for i in range(10):
  ans += num[i] * cost[i][1]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def min_ind_except_for_fixed(seq, fixed):
  m = float('inf')
  ind = -1
  for i in range(len(seq)):
    if not fixed[i] and seq[i] < m:
      ind = i
      m = seq[i]
  return ind


def dijkstra_mat(adj_matrix, start, goal):
  V = len(adj_matrix)
  assert V == 10
  cost = [float('inf')] * V    # cost[i] = (minimum cost from node_start to node_i)
  cost[start] = 0
  fixed = [False] * V
  for _ in range(V):
    u = min_ind_except_for_fixed(cost, fixed)
    fixed[u] = True
    for j in range(V):
      cost[j] = min(cost[j], cost[u] + adj_matrix[u][j])
  return cost[goal]



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

min_cost_change_to_1 = [dijkstra_mat(adj_matrix_weight, start=i, goal=1) for i in range(10)]
# print(min_cost_change_to_1)

total_min_cost = 0
for _ in range(h):
  line = list(map(int, input().split()))
  for num in line:
    if num != -1:
        total_min_cost += min_cost_change_to_1[num]

print(total_min_cost)

Submission status: Accepted

Solution code:
def solve():
    H, W = map(int,input().split())
    cost = [list(map(int,input().split())) for _ in range(10)]
    A = [list(map(int,input().split())) for _ in range(H)]
    d = []
    for i in range(10):
        d.append(dijkstra(i,10,cost))
    
    ans = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] != -1:
                ans += d[A[h][w]][1]
    
    print(ans)

def dijkstra(s,N,cost):
    d = [float("inf")] * N
    used = [False] * N
    d[s] = 0

    while True:
        v = -1
        for u in range(N):
            if not used[u] and (v == -1 or d[u] < d[v]):
                v = u
        if v == -1:
            break
        used[v] = True

        for u in range(N):
            d[u] = min(d[u], d[v] + cost[v][u])
    
    return d

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def solve():
    H, W = map(int,input().split())
    cost = [list(map(int,input().split())) for _ in range(10)]
    A = [list(map(int,input().split())) for _ in range(H)]
    d = warshall_floyd(cost, 10)
    
    ans = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] != -1:
                ans += d[A[h][w]][1]
    
    print(ans)

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

    
if __name__ == '__main__':
    solve()