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:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
c = [LIST() for _ in range(10)]
A = [LIST() for _ in range(H)]

#ワーシャルフロイド法  注意 PyPy非対応!!!!
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

graph = csr_matrix(c) #隣接行列からcsr行列をつくる
c = floyd_warshall(graph, directed=True) #無向の場合directed=True
#dist_matrixの中身はfloatになっているので注意！
	

#for i in range(10):
#	print(c[i])

import numpy as np
#距離
def distance(p1, p2):
	p1 = np.array(p1)
	p2 = np.array(p2) 
	return np.linalg.norm(p1-p2)
	

ans = 0
for i in range(H):
	for j in range(len(A[i])):
		if A[i][j] != -1:
			ans += c[A[i][j]][1]

print(int(ans))

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
c = [LIST() for _ in range(10)]
A = [LIST() for _ in range(H)]

#ワーシャルフロイド法  注意 PyPy非対応!!!!
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

graph = csr_matrix(c) #隣接行列からcsr行列をつくる
c = floyd_warshall(graph, directed=True) #無向の場合directed=True
#dist_matrixの中身はfloatになっているので注意！
	

#for i in range(10):
#	print(c[i])

import numpy as np
#距離
def distance(p1, p2):
	p1 = np.array(p1)
	p2 = np.array(p2) 
	return np.linalg.norm(p1-p2)
	

ans = 0
for i in range(H):
	for x in A[i]:
		if x == 1 or x == -1:
			continue
		else:
			ans += c[x][1]

print(int(ans))

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
c = [LIST() for _ in range(10)]
A = [LIST() for _ in range(H)]

#ワーシャルフロイド法  注意 PyPy非対応!!!!
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

graph = csr_matrix(c) #隣接行列からcsr行列をつくる
c = floyd_warshall(graph, directed=True) #有向の場合directed=True
#dist_matrixの中身はfloatになっているので注意！

#for i in range(10):
#	print(c[i])

ans = 0
for i in range(H):
	for x in A[i]:
		if x == 1 or x == -1:
			continue
		else:
			ans += c[x][1]

print(int(ans))

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
c = [LIST() for _ in range(10)]
A = [LIST() 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])

#for i in range(10):
#	print(c[i])

ans = 0
for i in range(H):
	for x in A[i]:
		if x == 1 or x == -1:
			continue
		else:
			ans += c[x][1]

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
d=[list(map(int,input().split())) for _ in range(10)]
e=[list(map(int,input().split())) for _ in range(h)]
def warshall_floyd(d,n):
    #d[i][j]=i番目の頂点からj番目の頂点までの最短距離
    for k in range(n+1):
        for i in range(n+1):
            for j in range(n+1):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
d=warshall_floyd(d,9)
ans=0
for i in range(h):
    for j in range(w):
        if e[i][j]>=0:
            ans+=d[e[i][j]][1]
print(ans)

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

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

res = 0
for a in A:
  for e in a:
    if e != -1 and e != 1:
      res += c[e][1]

print(res)

Submission status: Accepted

Solution code:
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=map(int,input().split())
c=[list(map(int,list(input().split()))) for _ in range(10)]
a=[list(map(int,list(input().split()))) for _ in range(h)]
e=[x[1] for x in warshall_floyd(10,c)]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
large_n = 100000000

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

A_mat = []
for i in range(H):
    A_mat.append(list(map(int, input().split())))
    



for k in range(10):
    for i in range(10):
        for j in range(10):
            C_mat[i][j] = min(C_mat[i][j], C_mat[i][k]+ C_mat[k][j])
            
            
            
            
ans = 0
for i in range(H):
    for j in range(W):
        if A_mat[i][j] != -1:
            ans += C_mat[A_mat[i][j]][1]
            
print(ans)

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    H, W = map(int, readline().split())
    L = list(list(map(int, readline().split())) for _ in range(10))
    path = dijkstra(csr_matrix(L))
    ans = 0
    for i in range(H):
        A = list(map(int, readline().split()))
        for j in range(W):
            a = A[j]
            if a!=-1:
                ans += path[a][1]
    print(int(ans))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
costMap = [list(map(int,input().split())) for _ in range(10)]
wall = [list(map(int,input().split())) for _ in range(H)]

memo = [float("INF")]*(10)
memo[1] = 0
flag = True
while flag:
    flag = False
    for i in range(10):
        for j in range(10):
            if memo[i]+costMap[j][i] < memo[j]:
                memo[j] = memo[i]+costMap[j][i]
                flag = True
ans = 0
for i in range(H):
    for j in range(W):
        a = wall[i][j]
        if a != -1:
            ans += memo[a]
print(ans)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque

inf = 10 ** 15
mod = 10 ** 9 + 7

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

print(ans)

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(10)]
s=[list(map(int,input().split())) for i in range(N)]
from scipy.sparse.csgraph import floyd_warshall
l=floyd_warshall(l)
ans=0
for i in s:
   for j in i:
      ans+=0 if j == -1 else l[j][1]
print(int(ans))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    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)

    dp = [[INF] * 10 for _ in range(10)]
    for i in range(10):
        for j in range(10):
            dp[i][j] = C[i][j]

    for k in range(10):
        for i in range(10):
            for j in range(10):
                tmp = dp[i][k] + dp[k][j]
                if tmp < dp[i][j]:
                    dp[i][j] = tmp

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
C=[]
for index1 in range(10):
    C.append(list(map(int,input().split())))
A=[]
for index2 in range(h):
    A.append(list(map(int,input().split())))

def warshall_floyd(G):

    #kがこの位置でなければならない
    for k in range(10):
        for i in range(10):
            for j in range(10):
                G[i][j]=min(G[i][j],G[i][k]+G[k][j])
    
    return G

D=warshall_floyd(C)
magic=[0]*10
for index3 in range(10):
    if index3!=1:
        magic[index3]=D[index3][1]

ans=0
for index4 in range(h):
    for index5 in range(w):
        if A[index4][index5]>-1:
            ans+=magic[A[index4][index5]]

print(ans)

Submission status: Accepted

Solution code:
def shortpath(C):
    #魔力表Cの任意のパスを最小化したい
    update = True
    while update:
        update = False
        for i in range(10):
            for j in range(10):
                for k in range(10):
                    if C[i][j] > C[i][k] + C[k][j]:
                        C[i][j] = C[i][k] + C[k][j]
                        update = True
    return C

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

    C = shortpath(C)
    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)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections

class WarshallFloyd():
    def __init__(self,N):  #Nは頂点の個数
        self.N = N
        self.d = [[float('inf')]*N for i in range(N)]  #d[i][j] = iからjへの最短距離,0-indexed
    def add(self,u,v,c,directed = False):
        if directed is False:  #無向グラフの場合
            self.d[u][v] = c
            self.d[v][u] = c
        else:  #有向グラフの場合
            self.d[u][v] = c
    def WarshallFloyd_search(self):
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(self.d[i][j],self.d[i][k] + self.d[k][j])
        for i in range(self.N):
            self.d[i][i] = 0
        return self.d

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

G = WarshallFloyd(10)

for i in range(10):
    for j in range(10):
        G.add(i,j,A[i][j],directed=True)

d = G.WarshallFloyd_search()

C = []
for i in range(10):
    C.append(d[i][1])

D = [0]*11
for i in range(H):
    for j in range(W):
        if B[i][j] == -1:
            D[10] += 1
        else:
            D[B[i][j]] += 1

ans = 0
for i in range(10):
    ans += C[i]*D[i]

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
grid = [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
d = [[float("inf")]*n for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for x in range(n):
    for y in range(n):
        d[x][y] = c[x][y]
        d[y][x] = c[y][x]
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
cost = warshall_floyd(d)
ans = 0
for h in range(H):
    for w in range(W):
        if grid[h][w] != -1:
            ans += cost[grid[h][w]][1]
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
# warshall_floyd法
def warshall_floyd(d,n):
 for k in range(n):
  for i in range(n):
   for j in range(n):
    d[i][j]= min(d[i][j],d[i][k]+d[k][j])
 return d

H,W = map(int,input().split())
# 隣接行列の定義、初期化
# ①コスト(存在しないときはinf)
d = [0 for i in range(10)]
# ②自分自身へのコストは０
for i in range(10):
 d[i] = list(map(int,input().split()))
ct=[0]*11
for i in range(H):
  lst=list(map(int,input().split()))
  for j in range(W):
   ct[lst[j]+1]+=1

A=warshall_floyd(d,10)
ans=0
for i in range(10):
 ans+=ct[(i+1)]*A[i][1]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):
    #print(*c, sep='\n')
    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(*c, sep='\n')
    cost = 0
    for a in A:
        for aa in a:
            if aa == -1:
                continue
            cost += c[aa][1]
    return cost


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    c = [[int(next(tokens)) for _ in range(9 - 0 + 1)] for _ in range(9 - 0 + 1)]  # type: "List[List[int]]"
    A = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  # type: "List[List[int]]"
    print(solve(H, W, c, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

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

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 = floyd_warshall(C)

ans = sum(d[a][1] for a in chain(*A) if a != -1)

print(int(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 = []
for i in range(h):
    a += list(map(int,input().split()))
C = Counter(a)
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,n in C.items():
    if i != -1:
        ans += c[i][1]*n
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
cost_mat = []
for i in range(10):
    cost_mat.append(list(map(int, input().split())))

for stop in range(10):
    for start in range(10):
        for end in range(10):
            cost_mat[start][end] = min(cost_mat[start][end], cost_mat[start][stop] + cost_mat[stop][end])
cost = 0
for h in range(H):
    in_ls = list(map(int, input().split()))
    for num in in_ls:
        if not num == -1:
            cost += cost_mat[num][1]
print(cost)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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):
                if C[i][j] > C[i][k] + C[k][j]:
                    C[i][j] = C[i][k] + C[k][j]
                    
    ans = 0
    for row in A:
        for n in row:
            if n != -1:
                ans += C[n][1]
    
    print(ans)
    return


if __name__ == '__main__':
    main()

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 _ in range(10)]
c = floyd_warshall(csgraph_from_dense(c))

result = 0
for _ in range(H):
    for i in map(int, input().split()):
        if i == -1:
            continue
        result += c[i][1]
print(int(result))

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
ma = [list(map(int,input().split())) for _ in range(10)]
for i in range(10):
    for j in range(10):
        for k in range(10):
            ma[j][k] = min(ma[j][k], ma[j][i]+ma[i][k])
li = [list(map(int,input().split())) for _ in range(h)]
ans = 0
for each_li in li:
    for l in each_li:
        if l!=-1:
            ans += ma[l][1]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3.4.3
import numpy as np
from scipy.sparse.csgraph import floyd_warshall, csgraph_from_dense
from itertools import*
from collections import*

h, w = map(int, input().split())
G = [list(map(int, input().split())) for _ in [0]*10]

m = floyd_warshall(csgraph_from_dense(G))

d = list(chain.from_iterable(list(map(int, input().split())) for _ in [0]*h))
C = Counter(d)
s = 0
for i in range(10):
    s += m[i][1] * C.get(i, 0)
print(int(s))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, deque
from copy import copy

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

d = defaultdict(lambda: float("inf"))
d["1_1"] = 0
nums = [i for i in range(10) if i != 1]

q = deque([[[1], 0]])

while q:
    tmp = q.pop()
    num, cost = tmp[0], tmp[1]
    if len(num) > 1:
        key = str(num[-1]) + "_1"
        d[key] = min(d[key], cost)
    if len(num) < 10:
        for n in nums:
            num_tmp = copy(num)
            if n not in set(num_tmp):
                num_tmp.append(n)
                q.append([num_tmp, cost + c[n][num_tmp[-2]]])

ans = 0
for i in range(H):
    for j in range(W):
        tmp = grid[i - 1][j - 1] 
        if tmp >= 0:
            ans += d[str(tmp) + "_1"]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import copy

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

d = dict()
nums = [i for i in range(10) if i != 1]
d["-1_1"] = 0

q = [[[1], 0]]

while q:
    tmp = q.pop()
    num, cost = tmp[0], tmp[1]
    key = str(num[-1]) + "_1"
    if d.get(key):
        d[key] = min(d[key], cost)
    else:
        d[key] = cost
    if len(num) < 10:
        for n in nums:
            num_tmp = copy.copy(num)
            if n not in set(num_tmp):
                num_tmp.append(n)
                q.append([num_tmp, cost + c[num_tmp[-1]][num_tmp[-2]]])

ans = 0
for i in range(H):
    for j in range(W):
        tmp = grid[i - 1][j - 1] 
        ans += d[str(tmp) + "_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

def abc079_d():
    inp = iter(map(int, read().split()))
    H, W = next(inp), next(inp)
    adj_mtx = [[next(inp) for _ in range(10)] for _ in range(10)]
    grid = [[next(inp) for _ in range(W)] for _ in range(H)]

    def floyd_warshall(W):
        ''' ワーシャルフロイド法、全頂点間の最短距離 '''
        n = len(W)  # 頂点の数
        # DPで全頂点間の最短距離を求める
        for k in range(n):
            for u in range(n):
                for v in range(n):
                    W[u][v] = min(W[u][v], W[u][k] + W[k][v])
        return W

    min_dist = floyd_warshall(adj_mtx)

    # グリッドの数字が-1と1以外はコスト発生するため足していく
    ans = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == -1 or grid[i][j] == 1:
                continue
            ans += min_dist[grid[i][j]][1]
    print(ans)

abc079_d()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def abc079_d():
    inp = iter(map(int, read().split()))
    H, W = next(inp), next(inp)
    adj_mtx = [[next(inp) for _ in range(10)] for _ in range(10)]
    grid = [[next(inp) for _ in range(W)] for _ in range(H)]

    import heapq
    def dijkstra(start, W):
        ''' スタート地点から到達可能なすべての頂点への最短距離を返す
            Pythonで学ぶアルゴリズムとデータ構造 P.111 一部変更
        '''
        # 仮の最短距離をinfに設定
        inf = 10**9
        distance_list = [inf] * len(W)
        # スタートの頂点だけ距離を0にする
        distance_list[start] = 0
        # 最短距離が確定した点
        done_list = []
        # 次に処理する頂点を決めるためのヒープ
        wait_heap = []
        for i, d in enumerate(distance_list):
            # (スタートからの距離, 頂点) のタプル
            heapq.heappush(wait_heap, (d, i))
        # ヒープが空になるまで処理を続ける
        while wait_heap:
            p = heapq.heappop(wait_heap)
            i = p[1]
            if i in done_list:
                continue
            # この時点でスタートからiへの距離が確定する
            done_list.append(i)
            # iに隣接するすべての頂点に対する処理
            for j, x in enumerate(W[i]):
                if x > -1 and j not in done_list:
                    # 緩和
                    d = min(distance_list[j], distance_list[i] + x)
                    distance_list[j] = d
                    # jへの仮の最短距離をdとしてヒープに追加
                    heapq.heappush(wait_heap, (d, j))
        return distance_list

    # 各点から1への距離(コスト)
    dist_to_1 = [None] * 10
    for i in range(10):
        dist_to_1[i] = dijkstra(i, adj_mtx)[1]

    # グリッドの数字が-1と1以外はコスト発生するため足していく
    ans = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == -1 or grid[i][j] == 1:
                continue
            ans += dist_to_1[grid[i][j]]
    print(ans)

abc079_d()

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 _ in range(h):
    A = list(map(int,input().split()))
    for a in A:
        if a==-1:
            continue
        else:
            ans += trans_map[a][1]
print(ans)

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 = []
for i in range(H):
    A.append(list(map(int,input().split())))

c2 = [[0 for _ in range(10)]for _ in range(10)]

for i in range(10):
    for j in range(10):
        c2[i][j] = c[i][j]+c[j][1]

d = []
for i in range(10):
    d.append(min(c2[i]))

for _ in range(10):
    c2 = [[0 for _ in range(10)]for _ in range(10)]
    for i in range(10):
        for j in range(10):
            c2[i][j] = c[i][j]+d[j]
    d = []
    for i in range(10):
        d.append(min(c2[i]))
su = 0
for i in range(H):
    for j in range(W):
        if A[i][j] >=0:
            su+=d[A[i][j]]
print(su)

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse as sps
import sys,math

h,w = map(int,input().split())
c = np.array([list(map(int,input().split()))for i in range(10)])
wf = sps.csgraph.floyd_warshall(c,directed=1).astype(int)

a = np.array([list(map(int,input().split()))for i in range(h)])

ans = 0
for arr in a:
    for num in arr:
        if num == -1: continue
        else: ans += wf[num][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 = []
for i in range(H):
    a += list(map(int, input().split()))

cost = [10**5]*10
cost[1] = 0
temp = [['1', 0]]

while temp:
    p = temp.pop()
    if len(p[0]) < 10:
        for s in '0123456789':
            if s in p[0]:continue
            else:
                nxt = p[1] + c[int(s)][int(p[0][-1])]
                if cost[int(s)] > nxt:
                    temp.append([p[0] + s, nxt])
                    cost[int(s)] = nxt
        
d = Counter(a)
ans = 0
for i in range(10):
    ans += d[i]*cost[i]
print(ans)