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:
def resolve():
    h, w = map(int, input().split())
    d = []
    # d[u][v] : 辺uvのコスト(存在しないときはinf)
    for i in range(10):
        d.append(list(map(int, input().split())))
    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])
    from scipy.sparse.csgraph import floyd_warshall
    cost = floyd_warshall(d)
    ans = 0
    for i in range(h):
        for j in map(int, input().split()):
            if j > -1:
                ans += cost[j][1]
    print("{:.0f}".format(ans))


resolve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    H,W=map(int,input().split())
    c=[list(map(int,input().split())) for _ in range(10)]
    l=[0]*10
    for _ in range(H):
        A=list(map(int,input().split()))
        for x in A:
            if x!=-1:
                l[x]+=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 i,x in enumerate(l):
        ans+=c[i][1]*x
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7

H, W = map(int, input().split())
INF = 10**10
N = 10
cost = [[INF]*N for _ in range(N)]

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

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

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

print (ans)

Submission status: Accepted

Solution code:
# solution

import io
import math

nim,mike = map(int,input().split())

array = [list(map(int,input().split())) for l in range(10)]

are = []

counter = 0

for _ in range(nim):
    are.extend(list(map(int,input().split())))

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

for sa in are:
    if sa != -1:
        counter += array[sa][1]

print(counter)

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
mp = [c[i][1] for i in range(10)]
mp.append(0)
for i in range(h):
    for j in range(w): ans += mp[a[i][j]]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
H, W = map(int,input().split())
C = []
V = 10
for _ in range(V):
    C.append(list(map(int,input().split())))
for k in range(V):
    for i in range(V):
        for j in range(V):
            C[i][j] = min(C[i][j], C[i][k] + C[k][j])
A = []
for _ in range(H):
    A += list(map(int,input().split()))
count = Counter(A)
ans = 0
for i in range(V):
    ans += count[i] * C[i][1]
print(ans)

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 _ in range(10)]
A = [list(map(int, input().split())) for _ in range(H)]
ans = 0
# print(*c, sep='\n')
# print(*A, sep='\n')
cost = floyd_warshall(c)
# print(*cost, sep='\n')
for i in range(H):
    for j in range(W):
        if A[i][j] == -1:
            continue
        ans += cost[A[i][j]][1]
        # print(ans)
print(int(ans))

Submission status: Accepted

Solution code:
import heapq

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

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


def dijkstra(start, goal, n, edge):
    d = [float("inf")] * n
    d[start] = 0
    q = [(0, start)]
    heapq.heapify(q)

    while q:
        ci, i = heapq.heappop(q)
        if d[i] < ci:
            continue

        for j in range(n):
            if j != start and j != i:
                if d[j] > d[i] + C[i][j]:
                    d[j] = d[i] + C[i][j]
                    heapq.heappush(q, (d[j], j))

    return d[goal]


cost = [0] * 10
for i in range(10):
    c = dijkstra(i, 1, 10, C)
    cost[i] = c

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

Submission status: Accepted

Solution code:

def wf(cost):
    l = 10
    for k in range(l):
        for i in range(l):
            for j in range(l):
                cost[i][j] =  min(cost[i][j],cost[i][k] + cost[k][j])

h,w = map(int,input().split())
c= []
for i in range(10):
    c.append(list(map(int,input().split())))
wf(c)
ans = 0
for i in range(h):
    for num in map(int,input().split()):
        if num==1 or num==-1:pass
        else:
            ans+=c[num][1]
print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
d = []
for i in range(10):
    a = list(map(int,input().split()))
    d.append(a)
def WF(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
WF(d)
L = []
for i in range(h):
    b = list(map(int,input().split()))
    L.append(b)
ans = 0
for i in range(h):
    for j in range(w):
        if L[i][j] == 1 or L[i][j] == -1:
            continue
        else:
            ans += d[L[i][j]][1]
print(int(ans))

Submission status: Accepted

Solution code:
def main():

    h,w = map(int,input().split())
    d = []
    for i in range(10):
        a = list(map(int,input().split()))
        d.append(a)
    def WF(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
    WF(d)
    L = []
    for i in range(h):
        b = list(map(int,input().split()))
        L.append(b)
    ans = 0
    for i in range(h):
        for j in range(w):
            if L[i][j] == 1 or L[i][j] == -1:
                continue
            else:
                ans += d[L[i][j]][1]
    print(int(ans))

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def main():
    import numpy as np

    h,w = map(int,input().split())
    d = np.zeros((10,10))
    for i in range(10):
        a = list(map(int,input().split()))
        d[i] = a
    def WF(b):
        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
    WF(d)
    L = []
    for i in range(h):
        b = list(map(int,input().split()))
        L.append(b)
    ans = 0
    for i in range(h):
        for j in range(w):
            if L[i][j] == 1 or L[i][j] == -1:
                continue
            else:
                ans += d[L[i][j]][1]
    print(int(ans))

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:

import numpy as np
from scipy.sparse.csgraph import floyd_warshall

h,w = map(int,input().split())
d = np.zeros((10,10))
for i in range(10):
    a = list(map(int,input().split()))
    d[i] = a
#print(d)
def WF(b):
    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
WF(d)
#d = floyd_warshall(d)
L = []
for i in range(h):
    b = list(map(int,input().split()))
    L.append(b)
ans = 0
for i in range(h):
    for j in range(w):
        if L[i][j] == 1 or L[i][j] == -1:
            continue
        else:
            ans += d[L[i][j]][1]
print(int(ans))

Submission status: Accepted

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

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

d = [[10**4]*10 for i in range(10)] 
for i in range(10):
    a = list(map(int,input().split()))
    for j in range(10):
      d[i][j] = a[j]
for i in range(10):
    d[i][i] = 0
    
ans = 0
chk = tuple(warshall_floyd(d))
for _ in range(h):
  c = list(map(int,input().split()))
  for i in c:
    if i != 1 and i != -1:
      ans += chk[i][1]
      
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n = 10
h,w = myinput()
c = mylistinput(n)
a = mylistinput(h)

d = [[float("inf")]*n for i in range(n)] 
# d[u][v]: 辺uvのコスト(存在しないときはinf)

for i in range(n):
    for j in range(n):
        cost = c[i][j]
        d[i][j] = cost

#自身のところに行くコストは０
for i in range(n):
    d[i][i] = 0

# ワーシャルフロイド（warshall_floyd）法
# d[u][v]: 辺uvのコスト(存在しないときはinf)
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

d = warshall_floyd(n,d)
# pprint(d)

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

Submission status: Accepted

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

H,W = imn()

D = [[INF for _ in range(10)] for _ in range(10)]
for i in range(10):
    c = iln()
    for j in range(10):
        D[i][j] = c[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])

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

Submission status: Accepted

Solution code:
import itertools
from collections import Counter
H, W = map(int, input().split())
cost = []
for i in range(10):
    cost.append(list(map(int, input().split())))
wall = []
for i in range(H):
    wall.append(list(map(int, input().split())))

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

wc = Counter(itertools.chain(*wall))
del wc[-1]
del wc[1]

ans = 0
for k, v in wc.items():
    ans += cost[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)]
A=[list(map(int,input().split())) for _ in range(H)]
#print(H,W,c,A)
to1=[0]*10
for i in range(10):
    dp=[[float("inf") for _ in range(10)] for _ in range(11)]
    dp[0][i]=0
    for j in range(10):
        for k in range(10):
            for l in range(10):
                dp[j+1][k]=min(dp[j+1][k],dp[j][l]+c[l][k])
        #print(dp)
        #input()
    to1[i]=dp[10][1]
    #print(to1)
mi=min(to1)
cnt=0
for i in range(H):
    for j in range(W):
        if A[i][j]==-1:
            cnt=cnt+mi
        else:
            cnt=cnt+to1[A[i][j]]
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

h, w = map(int, readline().split())
memo_graph = [list(map(int, readline().split())) for _ in range(10)]
cost = floyd_warshall(csr_matrix(memo_graph))
ans = 0
for i in range(h):
    for a in list(map(int, readline().split())):
        if a != -1:
            ans += cost[a][1]
print(int(ans))

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq

#全点最短距離(d[i][i]<0だと負閉路あり)
def warshall_floyd(n):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if(d[i][k] == INF or d[k][j] == INF):
          pass
        else:
          d[i][j] = min(d[i][j], d[i][k] + d[k][j])
  return

#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

INF = 1001001
H, W = map(int, input().split())
ans = 0

d = [list(map(int, input().split())) for _ in range(10)]
A = [list(map(int, input().split())) for _ in range(H)]
#G = [[INF for _ in range(10)] for _ in range(10)]
#for i in range(10):
#  for j in range(10):
#    G[i][j] = d[i][j]

warshall_floyd(10)

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from collections import Counter

H, W = map(int, input().split())
C = np.array([tuple(map(int, input().split())) for _ in range(10)])
A = Counter()
for _ in range(H):
    A.update(map(int, input().split()))
try:
    del A[-1]
except:
    pass

way = dijkstra(C.T, indices=1).astype(int)
print(sum(way[k] * v for k, v in A.items()))

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
d = []
for i in range(10):
  d.append(list(map(int,input().split())))
la = []
for i in range(H):
  la.append(list(map(int,input().split())))
#最短距離更新
for k in range(10):
  for s in range(10):
    for g in range(10):
      d[s][g] = min(d[s][g],d[s][k]+d[k][g])
#合計
ans = 0
for i in range(H):
  for j in range(W):
    a = la[i][j]
    if a != -1:
      ans += d[a][1]
print(ans)

Submission status: Accepted

Solution code:
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 = map(int, input().split())
ma = [ list(map(int,input().split(" "))) for i in range(10)]
sco = [ list(map(int,input().split(" "))) for i in range(h)]
a = csr_matrix(ma)
b = shortest_path(a)
ans = 0
for i in range(h):
  for j in range(w):
    num = sco[i][j]
    if num != -1:
      ans += b[num][1]
print(int(ans))

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from math import isinf


def warshall_floyd(matrix):
    """ ワーシャルフロイド
    :param matrix:  隣接行列(到達不能はfloat("inf"))
    :return matrix
    """
    # 到達不能をfloat("inf")にしておけば余計なチェックを入れなくても
    # inf > inf+(-1) のような到達不能＋負辺が繋がってしまうことはない
    V = len(matrix)  # 頂点数
    for i in range(V):
        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  # min(c1, c2+c3)
    return matrix


def init_matrix(V: int):
    """:param V: 頂点数
    """
    return [[float('inf')]*V for _ in range(V)]


H, W = map(int, input().split())
V = 10
matrix = init_matrix(V)
for i in range(10):
    c = map(int, input().split())
    for j, cj in enumerate(c):
        matrix[i][j] = cj

warshall_floyd(matrix)
costs = [matrix[i][1] for i in range(10)]

l = []
for _ in range(H):
    l.extend(list(map(int, input().split())))
c = Counter(l)
ans = 0


for k, v in c.items():
    if k == -1:
        continue
    ans += costs[k]*v
print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    h, w = map(int, input().split())
    cost_graph = []
    field = []
    for i in range(10):
        cost_graph.append(list(map(int, input().split())))

    for i in range(h):
        field.append(list(map(int, input().split())))

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

    ans = 0
    for y in range(h):
        for x in range(w):
            if field[y][x] == -1 or field[y][x] == 1:
                pass
            else:
                ans += cost_graph[field[y][x]][1]

    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
l = [list(map(int,input().split())) for i in range(10)]
a = [list(map(int,input().split())) for i in range(h)]
ans = 0
for rep in range(10):
    for i in range(10):
        for j in range(10):
            for k in range(10):
                if l[i][j] > l[i][k]+l[k][j]:
                    l[i][j] = l[i][k]+l[k][j]
num = [i[1] for i in l] + [0]
for i in a:
    for j in i:
        ans += num[j]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
h,w = map(int,input().split())
l = [list(map(int,input().split())) for i in range(10)]
a = [list(map(int,input().split())) for i in range(h)]
ans = 0
l = np.array(l)
for rep in range(10):
    for i in range(10):
        for j in range(10):
            for k in range(10):
                if l[i][j] > l[i][k]+l[k][j]:
                    l[i][j] = l[i][k]+l[k][j]
num = [i[1] for i in l] + [0]
for i in a:
    for j in i:
        ans += num[j]
print(ans)

Submission status: Accepted

Solution code:
def main():
    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 row in a:
        for cell in row:
            if ~cell:
                ans += c[cell][1]

    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
import numpy as np
C=np.array([list(map(int,input().split())) for _ in range(10)])

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

dp=np.array([[None]*10 for _ in range(10)])
for i in range(10):
  for j in range(10):
    dp[i][j]=C[i][j]
    
for _ in range(10): #更新回数最大10 -> 10回までは毎回良くなるかもしれない
  for i in range(10):
    for j in range(10):
      for k in range(0,9+1):
        dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
            
ans=0
for a in A:ans+=dp[a][1]
print(ans)

Submission status: Accepted

Solution code:
import collections
h,w = map(int,input().split())
c = []
wall = []


def judge(num):
    koho = collections.deque()
    for i in range(10):
        if dp[i] > dp[num] + c[i][num]:
            koho.append(i)
            dp[i] = dp[num] + c[i][num]
    if koho:
        here = koho.popleft()
        judge(here)



for i in range(10):
    c.append(list(map(int,input().split())))
for i in range(h):
    wall.extend(list(map(int,input().split())))
wall = collections.Counter(wall)
dp = [0] * 10
for i in range(10):
    dp[i] = c[i][1]
for i in range(10):
    judge(i)
ans = 0
wall = list(wall.items())
for i in range(len(wall)):
    if wall[i][0] == -1:
        pass
    else:
        ans += dp[wall[i][0]] * wall[i][1]
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
import numpy as np
C=np.array([list(map(int,input().split())) for _ in range(10)])

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


dp=np.array([[100100]*10 for _ in range(10)])
for i in range(0,10):
    for j in range(0,10):
        dp[i][j]=C[i][j]
        
for _ in range(10):
    for i in range(0,9+1):
        for j in range(0,9+1):
            for k in range(0,9+1):
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
            
ans=0
# print(dp)
for a in A:
    ans+=dp[a][1]
print(ans)

Submission status: Accepted

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

#dist[i][j] = iからjまでの最短距離
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])
    return dist

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

#全ての座標について、-1以外の時はコスト足していく（1⇒1は0なのでOK）
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, csgraph_from_dense
H, W = map(int, input().split())
c = [tuple(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)
C = floyd_warshall(G)

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

print(ans)

Submission status: Accepted

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

#dist[i][j] = iからjまでの最短距離を求める
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

#全ての座標について、-1以外の時はコスト足していく（1⇒1も0なのでOK）
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 collections import Counter
import sys
from math import isinf


def warshall_floyd(v_count: int):
    """ ワーシャルフロイド　(user:htkb)
    :param v_count: 頂点数
    :param matrix:  隣接行列(到達不能はfloat("inf"))
    """
    # 到達不能をfloat("inf")にしておけば余計なチェックを入れなくても
    # inf > inf+(-1) のような到達不能＋負辺が繋がってしまうことはない
    global matrix
    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  # min(c1, c2+c3)


H, W = map(int, input().split())
V = 10
matrix = [[float('inf')]*V for _ in range(V)]
for i in range(10):
    c = map(int, input().split())
    for j, cj in enumerate(c):
        matrix[i][j] = cj

warshall_floyd(V)
costs = [matrix[i][1] for i in range(10)]

l = []
for _ in range(H):
    l.extend(list(map(int, input().split())))
c = Counter(l)
ans = 0


for k, v in c.items():
    if k == -1:
        continue
    ans += costs[k]*v
print(ans)

Submission status: Accepted

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

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

    
x = warshall_floyd(x)
ans = 0
for i in range(h):
    s = list(map(int,input().split()))
    for j in range(w):
        if s[j] != -1:
            ans += x[s[j]][1]
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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)]

def warshallFloyd(num_v,am):
    """
    ワーシャルフロイド。All Pairs Shortest Path. APSP
    O(|V|^3)
    Parameters
    ----------
    num_v : int
        Number of nodes
    am : list[list[int]]
        adjacency matrix

    Returns
    -------
    list[list[int]]
        matrix of APSP

    """
    from math import isinf
    from copy import copy
    ret = copy(am)
    for k in range(num_v):
        for i in range(num_v):
            if isinf(ret[i][k]):
                continue
            for j in range(num_v):
                if isinf(ret[k][j]):
                    continue
                ret[i][j]=min(ret[i][j],ret[i][k]+ret[k][j])
    return ret

#隣接行列

wrsh_matrix = warshallFloyd(10,c)
ret = 0
for i in a:
    for j in i:
        if j < 0:
            continue
        ret += wrsh_matrix[j][1]
print(ret)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    H, W = (int(i) for i in input().split())
    c = [[int(i) for i in input().split()] for j in range(10)]
    A = [[int(i) for i in input().split()] for j in range(H)]
    from scipy.sparse.csgraph import dijkstra
    from scipy.sparse import csr_matrix
    d = dijkstra(csr_matrix(c))
    ans = 0
    for h in range(H):
        for w in range(W):
            cur = A[h][w]
            if cur == -1:
                continue
            ans += d[cur][1]
    print(int(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)]
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])
a = [list(map(int,input().split())) for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == -1:continue
        ans += abs(c[a[i][j]][1])
print(ans)