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

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

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

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

def func(fr, to, ignore):
    debug(fr, to, ignore)
    if fr == to:
        return 0
    res = c[fr][to]
    for md in range(10):
        if md in ignore:
            continue
        nignore = deepcopy(ignore)
        nignore.append(md)
        if tmp[fr][md] < inf:
            fr_md = tmp[fr][md]
        else:
            fr_md = func(fr, md, nignore)
        if tmp[md][to] < inf:
            md_to = tmp[md][to]
        else:
            md_to = func(md, to, nignore)
        debug(fr, md, to, fr_md, md_to)
        res = min(res, fr_md + md_to)
    tmp[fr][to] = res
    return res

h, w = MAP()
c = [LIST() for _ in range(10)]
a = [LIST() for _ in range(h)]

d = [[inf for _ in range(10)] for _ in range(10)]
tmp = [[inf for _ in range(10)] for _ in range(10)]
for i in range(10):
    for j in range(10):
        debug('a', i, j)
        d[i][j] = func(i, j, [i, j])
for i in range(10):
    debug(d[i])
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == -1:
            continue
        ans += d[a[i][j]][1]
        debug(d[a[i][j]][1])
print(ans)

Submission status: Accepted

Solution code:
def examA():
    O = SI()
    E = SI()
    ans = ""
    for i in range(len(O)+len(E)):
        if i%2==0:
            ans += O[i//2]
        else:
            ans += E[i//2]
    print(ans)
    return

def examB():
    A = LI()
    A.sort()
    ans = (A[2] - A[0]) // 2 + (A[2] - A[1]) // 2
    if (A[2]-A[0])%2==1:
        ans += 1
        if (A[2]-A[1])%2==0:
            ans += 1
    elif (A[2]-A[1])%2==1:
        ans += 2
    print(ans)
    return

def examC():
    S = SI()
    S.replace("RL","A")
    S.replace("LR","B")
    N = len(S)
    A = [0]*N
    print(S)
    l = 0; r = 0
    for i,s in enumerate(S):
        if s=="A":
            A[i] += r
        elif s=="B":
            A[i] += l
    ans = 0
    print(ans)
    return

def examD():
    def warshall_floyd(n, d):
        # 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 = LI()
    C = [LI()for _ in range(10)]
    A = [LI()for _ in range(H)]
    C = warshall_floyd(10,C)
    ans = 0
    for i in range(H):
        for j in range(W):
            a = A[i][j]
            if a==-1:
                continue
            ans += C[a][1]
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def floyd_warshall(dist):
    v = len(dist)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

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

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

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)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
c=[]
a=[]
b=0
for i in range(10):
    c.append(list(map(int,input().split())))
for i in range(h):
    a.append(list(map(int,input().split())))
for l in range(3):
    for i in range(10):
        for j in range(10):
            for k in range(10):
                c[i][j]=min(c[i][j],c[i][k]+c[k][j])
for i in range(h):
    for j in range(w):
        if a[i][j]!=-1:
            b+=c[a[i][j]][1]
print(b)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
h, w = map(int, input().split())
c = [ list(map(int, input().split())) for _ in range(10) ]
D = dijkstra(c)
C = D[:, 1].astype(int).tolist()
ans = 0
for _ in range(h):
  for i in map(int, input().split()):
    if i != -1:
      ans += C[i]
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(10)]
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 _ in range(H):
  a = list(map(int, input().split()))
  for x in a:
    if x != -1: res += d[x][1]
print(res)

Submission status: Accepted

Solution code:
def main():
    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)]
    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])
    answer = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] == -1:
                continue
            answer += cost[a[i][j]][1]
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
c=[list(map(int,input().split()))for _ in range(10)]
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])
co=[c[i][1] for i in range(10)]
ans=0
for _ in range(h):
	for i in list(map(int,input().split())):
		if i!=-1:ans+=co[i]
print(ans)

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

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

cost = [C[d][1] for d in range(10)]

ans = 0
for R in A:
    for a in R:
        if a == -1:
            continue
        ans += cost[a]
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

H, W = mi()
C = li2(10)
A = li2(H)

## ワーシャルフロイド法
for k in range(10):
    for j in range(10):
        for i in range(10):
            C[i][j] = min(C[i][j], C[i][k]+C[k][j])

## 各要素における最小コストを合計
ans = 0
for i in range(H):
    for j in range(W):
        if abs(A[i][j]) != 1:
            ans += C[A[i][j]][1]

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

H, W = mi()
C = li2(10)
A = li2(H)

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

H, W = mi()
C = li2(10)
a = li2(H)
memo = [C[i][1] for i in range(10)]
'''
tmp = -1
def dfs(column, m):
    if column == 1:
        global tmp
        tmp = max(m, tmp)
    for i in range(10):
        if i != column and C[column][i] < m:
            dfs(i, m-C[column][i])
    #return

for i in range(10):
    if i != 1:
        dfs(i, C[i][1])
        if tmp != -1:
            memo[i] = C[i][1] - tmp
        tmp = -1
'''
INF = 10**9
tmp = 10**9
'''
def dfs(col, m):
    if col == 1:
        global tmp
        tmp = min(m, tmp)
    for i in range(10):
        if i != col and m + C[col][i] < lim:
            dfs(i, m + C[col][i])

for i in range(10):
    if i != 1:
        tmp = INF
        lim = C[i][1]
        dfs(i, 0)
        memo[i] = min(tmp, memo[i])
'''
from collections import deque
for i in range(10):
    que = deque()
    lim = C[i][1]
    for j in range(10):
        if C[i][j] < lim:
            que.append([j, C[i][j]])
    while que != deque():
        #print(que)
        k = que.popleft()
        for j in range(10):
            if C[k[0]][j] + k[1] < lim and k[0] != j:
                if j == 1:
                    memo[i] = min(memo[i], C[k[0]][j] + k[1])
                else:
                    que.append([j, C[k[0]][j] + k[1]])

ans = 0
for i in range(H):
    for j in range(W):
        if abs(a[i][j]) != 1:
            ans += memo[a[i][j]]

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

H, W = mi()
C = li2(10)
a = li2(H)
memo = [C[i][1] for i in range(10)]
flag = -1
'''
def dfs(column, m):
    if column == 1:
        global flag
        flag = max(m, flag)
    for i in range(10):
        if i!=column and C[column][i] < m:
            dfs(i, m-C[column][i])
    #return

for i in range(10):
    if i != 1:
        dfs(i, C[i][1])
        if flag != -1:
            memo[i] = C[i][1]-flag
        flag = -1
'''
flag = 10**9

def dfs(col, m):
    if col == 1:
        global flag
        flag = min(m, flag)
    for i in range(10):
        if i != col and m + C[col][i] < lim:
            dfs(i, m + C[col][i])

for i in range(10):
    if i != 1:
        flag = 10**9
        lim = C[i][1]
        dfs(i, 0)
        if flag != 10**9:
            memo[i] = flag

ans = 0
for i in range(H):
    for j in range(W):
        if abs(a[i][j]) != 1:
            ans += memo[a[i][j]]

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
'''
def check(A):
    num = A[1]
    for i in range(10):
        if A[i] >= num and i!=1:
            A[i] = INF
    print('check', A)
    for i in range(10):
        if A[i]!=INF and A[i]!=0 and i!=1:
                return True
    return False


def dfs(A):
    k = check(A)
    while k:
        for i in range(10):
            if i!= 1 and A[i] != INF:
                for j in range(10):
                    if A[j] != INF:
                        A[j] = min(A[i]+C[i][j], A[j])
                        if j == 1 and A[j]==A[i]+C[i][j]:
                            A[i] = INF
        print('dfs', A)
        k = check(A)
    print(A)
    return A[1]

    

H, W = mi()
C = li2(10)
a = li2(H)
ans = 0

INF = 10**9
memo = [INF]*10

for i in range(10):
    if i!= 1:
        A = []
        for j in range(10):
            A.append(C[i][j])
        print(A)
        memo[i] = dfs(A)
        print(i, memo[i])

for i in range(H):
    for j in range(W):
        if a[i][j] != -1 and a[i][j] != 1:
            ans += memo[a[i][j]]

print(memo)

print(ans)
'''
H, W = mi()
C = li2(10)
a = li2(H)
memo = [C[i][1] for i in range(10)]
flag = -1

def dfs(column, m):
    #print('a')
    if column == 1:
        global flag
        flag = max(m, flag)
    for i in range(10):
        if i!=column and C[column][i] < m:
            dfs(i, m-C[column][i])
    return False

for i in range(10):
    if i != 1:
        dfs(i, C[i][1])
        #print(flag)
        if flag != -1:
            memo[i] = C[i][1]-flag
            #print(i, flag)
        flag = -1
    #print(memo)

ans = 0

for i in range(H):
    for j in range(W):
        if abs(a[i][j]) != 1:
            ans += memo[a[i][j]]
#print(memo)
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
INF = 10000
G = [[INF] * 10 for _ in range(10)]
for i in range(10):
    G[i][i] = 0

for i in range(10):
    for j, n in enumerate(map(int, input().split())):
        G[i][j] = n

for k in range(10):
    for i in range(10):
        if G[i][k] == INF:
            continue
        for j in range(10):
            if G[k][j] == INF:
                continue
            G[i][j] = min(G[i][j], G[i][k] + G[k][j])

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

# print(G)
magic = [INF] * 10
for i in range(10):
    magic[i] = G[i][1]
# print(magic)
ans = 0

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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
list_C = [ list(map(int,input().split(" "))) for i in range(10)]
list_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):
            list_C[i][j] = min(list_C[i][j], list_C[i][k]+list_C[k][j])
ans = 0
for i in range(h):
    for j in range(w):
        num = list_A[i][j]
        if num != -1:
            ans += list_C[num][1]
print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd(G, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])

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)]
warshall_floyd(c, 10)
ans = 0
for b in a:
    for i in b:
        if not i == -1:
            ans += c[i][1]
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
C = [list(map(int, input().split())) for j in range(10)]
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])
 
S = 0
for i in range(H):
    for x in list(map(int, input().split())):
        if x != -1:
            S += C[x][1]
print(S)

Submission status: Accepted

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

S = 0
for i in range(H):
    for x in list(map(int, input().split())):
        if x != -1:
            S += C[x][1]
print(S)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

h, w = na()
c = nan(10)
a = nan(h)

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

def main():
    dist = [[inf] * 10 for _ in range(10)]
    for i in range(10):
        for j in range(10):
            dist[i][j] = c[i][j]
    floyd_warshall(10, dist)
    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)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
H, W = map(int,input().split())
min_cost = [float("inf")] * 10
min_cost[1] = 0
costs = [list(map(int,input().split())) for _ in range(10)]
que = [(0, 1)]
while que:
    cost, v = heappop(que)
    if cost != min_cost[v]:
        continue
    for to in range(10):
        if min_cost[to] > cost + costs[to][v]:
            min_cost[to] = cost + costs[to][v]
            heappush(que, (min_cost[to], to))
ans = 0
for i in range(H):
    for ch in list(map(int,input().split())):
        if ch != -1:
            ans += min_cost[ch]
print(ans)

Submission status: Accepted

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


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

shortest_path = list(zip(*graph))[1]
ans = 0
for _ in range(h):
    for a in map(int, input().split()):
        if a == -1:
            continue
        ans += shortest_path[a]
print(ans)

Submission status: Accepted

Solution code:
import heapq
h, w = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(10)]

trans_graph = list(zip(*graph))
next_nodes = []
for idx, d in enumerate(trans_graph[1]):
    next_nodes.append((d, idx))
heapq.heapify(next_nodes)

INF = 10**9
decided = [0]*10
decided[1] = 1
dist = [INF]*10
dist[1] = 0

while next_nodes:
    distance, v = heapq.heappop(next_nodes)
    if decided[v]:
        continue
    decided[v] = 1
    dist[v] = distance
    for v2, x in enumerate(trans_graph[v]):
        if decided[v2]:
            continue
        heapq.heappush(next_nodes, (dist[v]+x, v2))

ans = 0
for _ in range(h):
    for x in map(int, input().split()):
        if x == -1:
            continue
        ans += dist[x]

print(ans)

Submission status: Accepted

Solution code:
import heapq
h, w = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(10)]

trans_graph = list(zip(*graph))
next_nodes = []
for idx, d in enumerate(trans_graph[1]):
    next_nodes.append((d, idx))

heapq.heapify(next_nodes)

INF = 10**9
decided = [0]*10
decided[1] = 1
dist = [INF]*10
dist[1] = 0
while 0 in decided:
    distance, v = heapq.heappop(next_nodes)
    if decided[v]:
        continue
    decided[v] = 1
    dist[v] = distance
    for v2, x in enumerate(trans_graph[v]):
        if decided[v2]:
            continue
        heapq.heappush(next_nodes, (dist[v]+x, v2))

ans = 0
for _ in range(h):
    for x in map(int, input().split()):
        if x == -1:
            continue
        ans += dist[x]

print(ans)

Submission status: Accepted

Solution code:
# ワーシャルフロイド　全点最短経路、負の距離あっても可　o(n**3)
def warshall_floyd(d):
    #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()) #n:頂点数　m:辺の数
n=10
d = [list(map(int, input().split())) for i in range(n)]
a= [list(map(int, input().split())) for i in range(h)]

x=warshall_floyd(d)

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

Submission status: Accepted

Solution code:
from collections import Counter

H, W = map(int, input().split())
graph = [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):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

ctr = Counter(sum(A, []))
ans = 0
for i, c in ctr.items():
    if i == -1:
        continue
    ans += graph[i][1] * c
print(ans)

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

DP = [[0] * 10 for _ in range(9)]
for i in range(9):
    for j in range(10):
        if i == 0:
            DP[i][j] = C[j][1]
        else:
            DP[i][j] = min(DP[i - 1][k] + C[j][k] for k in range(10))

answer = 0
for i in range(h):
    for j in range(w):
        if A[i][j] == -1:
            continue
        answer += DP[-1][A[i][j]]

print(answer)

Submission status: Accepted

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

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)]
d_list = [0]*10 
ans = 0
warshall_floyd(c,d_list)

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

Submission status: Accepted

Solution code:
import copy

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

#print(c)
#print(H)

#１からの最短経路を求めよ

dp=copy.deepcopy(c)

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

ans=0
for y in range(H):
    for x in range(W):
        if A[y][x] != -1:
            ans += dp[A[y][x]][1]
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
from collections import defaultdict
h, w = map(int, input().split())
table = [list(map(int, input().split())) for _ in range(10)]
dd = defaultdict(int)
for _ in range(h):
    for x in map(int, input().split()):
        if x == -1:
            continue
        dd[x] += 1

trans_table = list(zip(*table))
scores = dijkstra(csgraph_from_dense(trans_table), indices=1)

ans = 0
for k, v in dd.items():
    ans += int(scores[k])*v
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
from collections import defaultdict
h, w = map(int, input().split())
table = [list(map(int, input().split())) for _ in range(10)]
dd = defaultdict(int)
for _ in range(h):
    for x in map(int, input().split()):
        if x == -1:
            continue
        dd[x] += 1

trans_table = list(zip(*table))
scores = dijkstra(csr_matrix(trans_table), indices=1)
ans = 0
for k, v in dd.items():
    ans += int(scores[k])*v
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
h, w = map(int, input().split())
table = [list(map(int, input().split())) for _ in range(10)]
dd = defaultdict(int)
for _ in range(h):
    for x in map(int, input().split()):
        if x == -1:
            continue
        dd[x] += 1

INF = 10**9
scores = [INF]*10
decided = [0]*10
queue = deque()
trans_table = list(zip(*table))
for i in range(10):
    x = trans_table[1][i]
    scores[i] = x

MIN = min(set(scores) ^ {0})

while 0 in decided:
    for idx, score in enumerate(scores):
        if score <= MIN:
            decided[idx] = 1

    for i in range(10):
        if i == 1:
            continue
        if decided[i]:
            for j in range(10):
                if not decided[j]:
                    queue.append((i, j))

    while queue:
        i, j = queue.popleft()
        x = trans_table[i][j]
        scores[j] = min(scores[j], scores[i]+x)

    MIN += 1



ans = 0
for k, v in dd.items():
    ans += scores[k]*v
print(ans)

Submission status: Accepted

Solution code:
# むずかしい
from itertools import chain
from collections import Counter

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

ct = Counter(chain(*a))
ans = sum(ct[i] * c[i][1] for i in range(10))
print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
cij = [[int(i) for i in input().split()] for j in range(10)]
aij = [[int(i) for i in input().split()] for j in range(h)]

#print(cij,aij)





#exit()
"""
for i in range(10):
	mat[i][i]=0
"""

mat = cij
"""
for i in range(M):
	u,v,l=map(int,input().split())
	mat[u][v] = l
	mat[v][u] = l
"""
for i in range(10):
	for x in range(10):
		for y in range(10):
			mat[x][y] = min(mat[x][y], mat[x][i] + mat[i][y])
#print(mat)
ans = 0

for i in range(h):
    for j in range(w):
        if aij[i][j] != -1 and aij[i][j] != 1:
            #print(aij[i][j])
            ans += mat[aij[i][j]][1]

print(ans)

Submission status: Accepted

Solution code:
[H,W] = [int(s) for s in input().rstrip().split(" ")]
L = []
for num in range(10):
  L.append([int(s) for s in input().rstrip().split(" ")])
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])
k = 0
for h in range(H):
  L_h = [int(s) for s in input().rstrip().split(" ")]
  for x in L_h:
    if x != -1:
      k += L[x][1]
print(k)