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:
from scipy.sparse.csgraph import floyd_warshall
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)]

d = floyd_warshall(C)
cnt = 0
for arr in A:
  for i in arr:
    if i != -1:
      cnt += d[i][1]
      
print(int(cnt))

Submission status: Accepted

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

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

cost=[C[i][1] for i in range(10)]
cnt=0
for i in range(h):
    for j in range(w):
        if W[i][j]!=-1:
            cnt +=cost[W[i][j]]

print(cnt)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
c = [0 for _ in range(10)]
for i in range(10):
  c[i] = list(map(int, input().split()))
A = [0 for _ in range(H)]
for i in range(H):
  A[i] = list(map(int, input().split()))
for k in range(10):
  for i in range(10):
    for j in range(10):
      c[i][j] = min(c[i][j], c[i][k] + c[k][j])
ans = 0
for 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:
from scipy.sparse.csgraph import floyd_warshall

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

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

ans = 0
for i in range(H):
    a = list(map(int, input().split()))
    for j in a:
        if j != -1 and j != 1:
            ans += d[j][1]

print(int(ans))

Submission status: Accepted

Solution code:
import copy
from collections import Counter

def make_table():
    dp = copy.deepcopy(C)

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


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

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

cntA = Counter(A)

dp = make_table()

print(sum([dp[key][1] * cntA[key] if key != -1 else 0 for key in cntA]))

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
c = []
dicta = {}
dicta[-1] = 0
for i in range(10):
    c.append(list(map(int,input().split())))
    dicta[i] = 0
c = [i for i in zip(*c)]
for i in range(H):
    a = list(map(int,input().split()))
    for i in a:
        dicta[i] += 1
dicta.pop(-1)
cost = [0 for i in range(10)]
def dijkstra_heap(start,node,cost):
    import heapq
    d = [float('inf') for i in range(node)]
    d[start] = 0
    d2 = [[0,start]]
    heapq.heapify(d2)
    while d2:
        c,v = heapq.heappop(d2)
        if d[v] < c:
            continue
        for j in range(node):
            if d[j] > d[v]+cost[v][j]:
                d[j] = d[v]+cost[v][j]
                heapq.heappush(d2,[d[j],j])
    return d

cost = dijkstra_heap(1,10,c)
ans = 0
for k,v in dicta.items():
    ans += v*cost[k]
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
c = []
dicta = {}
dicta[-1] = 0
for i in range(10):
    c.append(list(map(int,input().split())))
    dicta[i] = 0
c = [i for i in zip(*c)]
for i in range(H):
    a = list(map(int,input().split()))
    for i in a:
        dicta[i] += 1
dicta.pop(-1)
cost = [0 for i in range(10)]
def dijkstra_heap(start,node,cost):
    import heapq
    d = [float('inf') for i in range(node)]
    used = [False for i in range(node)]
    d[start] = 0
    d2 = [[0,start]]
    heapq.heapify(d2)
    while d2:
        c,v = heapq.heappop(d2)
        if used[v]:
            continue
        used[v] = True
        for j in range(node):
            d[j] = min(d[j],d[v]+cost[v][j])
            if not used[j]:
                heapq.heappush(d2,[d[j],j])
    return d

cost = dijkstra_heap(1,10,c)
ans = 0
for k,v in dicta.items():
    ans += v*cost[k]
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
c = []
dicta = {}
dicta[-1] = 0
for i in range(10):
    c.append(list(map(int,input().split())))
    dicta[i] = 0
c = [i for i in zip(*c)]
for i in range(H):
    a = list(map(int,input().split()))
    for i in a:
        dicta[i] += 1
dicta.pop(-1)
cost = [0 for i in range(10)]
def dijkstra_heap(start,node,cost):
    import heapq
    d = [float('inf') for i in range(node)]
    used = [False for i in range(node)]
    d[start] = 0
    d2 = [[0,start]]
    heapq.heapify(d2)
    while True:
        flag = True
        while d2:
            c,v = heapq.heappop(d2)
            if not used[v]:
                flag = False
                break
        if flag:
            break
        used[v] = True
        for j in range(node):
            d[j] = min(d[j],d[v]+cost[v][j])
            heapq.heappush(d2,[d[j],j])
    return d

cost = dijkstra_heap(1,10,c)
ans = 0
for k,v in dicta.items():
    ans += v*cost[k]
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
c = []
dicta = {}
dicta[-1] = 0
for i in range(10):
    c.append(list(map(int,input().split())))
    dicta[i] = 0
c = [i for i in zip(*c)]
for i in range(H):
    a = list(map(int,input().split()))
    for i in a:
        dicta[i] += 1
dicta.pop(-1)
cost = [0 for i in range(10)]
def dijkstra(start,node,cost):
    d = [float('inf') for i in range(node)]
    used = [False for i in range(node)]
    d[start] = 0
    while True:
        flag = True
        for i in range(node):
            if (not used[i]) and flag:
                v = i
                flag = False
            elif (not used[i]) and d[i] < d[v]:
                v = i
        
        if flag:
            break
        used[v] = True
        for j in range(node):
            d[j] = min(d[j],d[v]+cost[v][j])
    return d

cost = dijkstra(1,10,c)
ans = 0
for k,v in dicta.items():
    ans += v*cost[k]
print(ans)

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
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])
print(sum(C[k][1]*v for k, v in Counter(a for aa in A for a in aa).items() if abs(k) != 1))

Submission status: Accepted

Solution code:
h,w = map(int,input().split())

C = []
for i in range(10):
    C.append(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

trans_map = warshall_floyd(C)

ans = 0
for i in range(h):
    line = list(map(int,input().split()))
    for j in range(w):
        num = line[j]
        if num == -1:
            continue
        ans += trans_map[num][1]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
# https://atcoder.jp/contests/arc067/tasks/arc067_a
# C - Factors of Factorial
"""
m > n impossible
m = n, possible only when n = 1


"""

H = gi()
W = gi()
cs = [[0 for x in range(10)] for i in range(10)]

for i in range(10):
    for j in range(10):
        cs[i][j] = gi()

for mid in range(10):
    for u in range(10):
        for v in range(10):
            cs[u][v] = min(cs[u][v], cs[u][mid] + cs[mid][v])
            cs[v][u] = min(cs[v][u], cs[v][mid] + cs[mid][u])

ans = 0
for i in range(H):
    for j in range(W):
        a = gi()
        if a >= 0:
            ans += cs[a][1]
print(ans)

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):
            if c[i][j] > c[i][k] + c[k][j]:
                c[i][j] = c[i][k] + c[k][j]
ans = 0
for i in range(h):
    a = list(map(int, input().split()))
    for j in range(w):
        if a[j] >= 0:
            ans += c[a[j]][1]
print(ans)

Submission status: Accepted

Solution code:
# AGC079 D - Wall
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]>=0:
            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 row in A:
    for a in row:
        if a < 0:
            continue
        ans += c[a][1]
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall
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)]
g=csgraph_from_dense(c,null_value=0)
d=floyd_warshall(g)
ans=0
for i in range(h):
  for j in range(w):
    if a[i][j]!=-1:
      ans+=d[a[i][j]][1]
print(int(ans))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
import numpy as np
H,W=map(int,input().split(' '))
c = np.array([list(map(int,input().split(' '))) for i in range(10)])
A = [list(map(int,input().split(' '))) for i in range(H)]
csr = csr_matrix(c)
cost  = dijkstra(csr)
ans = 0
for i in A:
    for j in i:
        if j != -1:
            ans += cost[j][1]
print(int(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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):
    #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
n=10
B=warshall_floyd(c)
#print(B)
ans=0
for i in range(H):
    for j in range(W):
        if A[i][j]==-1 or A[i][j]==1:
            continue
        else:
            ans+=B[A[i][j]][1]
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())

WF = []
wall = []
ans = 0

for _ in range(10):
    array = list(map(int, input().split()))
    WF.append(array)

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

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

for i in range(h):
    for j in range(w):
        num = wall[i][j]
        if num != -1:
            ans += WF[num][1]

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
WF=[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):
            WF[i][j]=min(WF[i][j],WF[i][k]+WF[k][j])

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

Submission status: Accepted

Solution code:
# ABC79 D - Wall
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 f_warshall(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])

f_warshall(C)

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

print(int(cost))

Submission status: Accepted

Solution code:
# ABC79 D - Wall
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 f_warshall(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])

f_warshall(C)

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

print(int(cost))

Submission status: Accepted

Solution code:
# ABC79 D - Wall
from scipy.sparse.csgraph import floyd_warshall

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

C = floyd_warshall(C)  

cost = 0
for i in range(H):
    for a in A[i]:
        if a != -1:
            cost += C[a][1]

print(int(cost))

Submission status: Accepted

Solution code:
# ABC79 D - Wall
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

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

C = floyd_warshall(C)  

cost = 0
for i in range(H):
    for a in A[i]:
        if a != -1:
            cost += C[a][1]

print(int(cost))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

H, W = map(int, input().split())
C = [[0]*10 for _ in range(10)]
A = [[0]*W for _ in range(H)]

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

C = floyd_warshall(C)  

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

print(int(cost))

Submission status: Accepted

Solution code:
INFTY = 10**4
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 = [[INFTY for _ in range(10)] for _ in range(10)]
for i in range(10):
    for j in range(10):
        d[i][j] = C[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])

cnt = 0
for i in range(H):
    for j in range(W):
        if A[i][j]>-1:
            cnt += d[A[i][j]][1]
print(cnt)

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

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

#各数字を1に変えるための最小の魔力を求める
#ワーシャルフロイド法
dp=[[1000*10 for _ in range(10)] for __ in range(10)]
for i in range(10):
    for j in range(10):
        dp[i][j]=C[i][j]
for i in range(10): #直前の数字
    for j in range(10): #最初の数字
        for k in range(10): #変化後の数字
            dp[j][k]=min(dp[j][k],dp[j][i]+dp[i][k])
min_mp=[0]*10
for i in range(10):
    min_mp[i]=dp[i][1]

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc079/tasks/abc079_d

from collections import Counter
from functools import reduce

def warshall(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]

h,w = map(int,input().split())
magic = [list(map(int,input().split())) for _ in range(10)]
counter = Counter()
[counter.update(Counter(map(int, input().split()))) for _ in range(h)]
warshall(magic, 10)
print(reduce(lambda x,y:x+y, [magic[k][1] * v for k,v in counter.items() if k > -1]))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc079/tasks/abc079_d

from collections import Counter
from functools import reduce

def warshall(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]

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

counter = Counter()
for _ in range(h):
    counter.update(Counter(map(int, input().split())))
warshall(magic, 10)
print(reduce(lambda x,y:x+y, [magic[k][1] * v for k,v in counter.items() if k > -1]))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc079/tasks/abc079_d

from collections import Counter
from functools import reduce

def warshall(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]

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

counter = {i:0 for i in range(10)}
for _ in range(h):
    for a in map(int, input().split()):
        if a > -1:
            counter[a] += 1
    # counter.update(Counter(map(int, input().split())))
warshall(magic, 10)

ans = 0
for k,v in counter.items():
    ans += magic[k][1] * v
print(ans)
# print(reduce(lambda x,y:x+y, [magic[k][1] * v for k,v in counter.items() if k > -1]))

Submission status: Accepted

Solution code:
def main():
    h,w = map(int,input().split())
    c = []
    for i in range(0,10):
        cc = list(map(int,input().split()))
        c.append(cc)
    a = []
    for i in range(0,h):
        aa = list(map(int,input().split()))
        a.append(aa)
    # ワーシャルフロイド（最短経路だす）
    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])
    cnt = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] != 1 and a[i][j] >= 0:
                cnt += c[a[i][j]][1]
    print(cnt)


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    h,w = map(int,input().split())
    c = []
    for i in range(0,10):
        cc = list(map(int,input().split()))
        c.append(cc)
    a = []
    for i in range(0,h):
        aa = list(map(int,input().split()))
        a.append(aa)
    # ワーシャルフロイド（最短経路だす）
    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])
    cnt = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] == -1:
                continue
            else:
                cnt += c[a[i][j]][1]
    print(cnt)


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

# C[i][j]はiをjにするのに必要なコスト
# warshal-floyd
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 += 0
        else:
            ans += C[A[i][j]][1]
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph._shortest_path import floyd_warshall


def solve():
    H, W = map(int, input().split())
    c = [[] for _ in range(10)]
    for i in range(10):
        c[i] = list(map(int, input().split()))
    A = [[] for _ in range(H)]
    for i in range(H):
        A[i] = list(map(int, input().split()))
    
    fw = floyd_warshall(csr_matrix(c))
    power = [0 for _ in range(10)]
    for i in range(10):
        if i == 1:
            continue
        power[i] = fw[i][1]
    
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == -1 or A[i][j] == 1:
                continue
            ans += power[A[i][j]]
    print(int(ans))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# ワーシャルフロイドで解くバージョン
h, w = map(int, input().split())
INF = 10 ** 10
table = [[INF] * 10 for _ in range(10)]

for i in range(10):
    column = list(map(int, input().split()))
    for j in range(10):
        if i == j:
            continue
        table[i][j] = column[j]

wall = {}
for _ in range(h):
    for a in list(map(int, input().split())):
        if a not in wall:
            wall[a] = 1
        else:
            wall[a] += 1

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

ans = 0
for k, v in wall.items():
    if k != -1 and k != 1:
        ans += table[k][1] * v
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
C = [list(map(int,input().split())) for _ in range(10)]
cntA = {}
for _ in range(H):
  for a in map(int,input().split()):
    if a not in cntA:
      cntA[a] = 1
    else:
      cntA[a] += 1

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 key, num in cntA.items():
  if key not in [-1,1]:
    ans += C[key][1]*num
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

from scipy.sparse.csgraph import floyd_warshall

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

H, W = MAP()
G = build_grid(10, 10, 0, int)
grid = build_grid(H, W, 0, int)

# 全頂点(数字0~9)間の最短距離
wf = floyd_warshall(G)

ans = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] != -1:
            a = grid[i][j]
            # 数字aを1に変える最小コスト
            ans += int(wf[a,1])
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np 
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

I = np.array(sys.stdin.read().split(), dtype=np.int64)
h, w = I[:2]
c = I[2:102].reshape(10, 10).T
a = I[102:].reshape(h, w)
                                                              
def main():
    cost = dijkstra(csr_matrix(c), directed=True, indices=1).astype(np.int64)

    return np.sum(cost[a[a != -1]])

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np 
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

I = np.array(sys.stdin.read().split(), dtype=np.int64)
h, w = I[:2]
c = I[2:102].reshape(10, 10)
a = I[102:].reshape(h, w)
                                                              
def main():
    cost = floyd_warshall(csr_matrix(c), directed=True).astype(np.int64)
    
    res = cost[a[a != -1], 1]
    return np.sum(res)

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	H, W = MAP()
	TABLE = [MAP() for _ in range(10)]
	A = [MAP() for _ in range(H)]

	to_one = [t[1] for t in TABLE]
	queue = deque([i for i in range(10)])
	
	while queue:
		# print(queue)
		mi = queue.popleft()
		for i, t in enumerate(TABLE):
			if i == mi: continue
			if t[mi]+to_one[mi] < to_one[i]:
				to_one[i] = t[mi]+to_one[mi]
				queue.append(i)
	
	# print(to_one)
	
	ans = 0
	for row in A:
		for a in row:
			if a != -1: ans += to_one[a]
	
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#理解のためにワーシャルフロイドで解いてみる

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

#参考ページ：https://dai1741.github.io/maximum-algo-2012/docs/shortest-path/

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

ans=0

for i in a:
  for j in i:
    if j!=-1:
      ans+=li[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 i in range(10):
    for j in range(10):
        for k in range(10):
            c[j][k]=min(c[j][k],c[j][i]+c[i][k])
ans=0
for i in range(h):
    for j in range(w):
        if a[i][j]!=-1:
            ans+=c[a[i][j]][1]
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import shortest_path


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

graph = np.zeros((10,10))
for i in range(10):
    for j in range(10):
        graph[i,j] = c[i][j]
dist = shortest_path(graph,directed=True).astype(int)

#print(dist)
res=0
for i in range(h):
    #print(a[i])
    for j in range(w):
        if a[i][j]==-1:continue
        res+=dist[a[i][j]][1]
        #print(dist[a[i][j]][1])
print(res)

Submission status: Accepted

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

#0と2～9について、（同じ数字を経由するのはありえないことを利用して）
#全探索で「1にするのに必要なエネルギー」の最小値を求める。

seq=(0,1,2,3,4,5,6,7,8,9)
mi=[float("inf")]*10 #各数字から1にするのにかかる最小値を記録する配列

import itertools
for ptn in itertools.permutations(seq):
  num=ptn[0] #今調べる始点数値がどれか。
  en=0 #1までにするのに必要なエネルギー量を記録。
  for i in range(9):
    if ptn[i]==1:
      break
    else:
      en+=li[ptn[i]][ptn[i+1]]
  mi[num]=min(mi[num], en)

ans=0

for i in a:
  for j in i:
    if j!=-1:
      ans+=mi[j]
print(ans)