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 collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])

def graphm():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(m):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((w,b))
        g[b].append((w,a))
    return n,m,g

def warshall_floyd(): # d[i][j]: iからjへの最短距離
    h,w = map(int,input().split()) #n:頂点数　w:辺の数
    d = []
    for _ in range(10):
        d.append(inpl())
    n=10
    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])
    a=[]
    for _ in range(h):
        a.append(inpl())
    pre = []
    for i in range(10):
        pre.append(d[i][1])
    check = defaultdict(int)
    for i in range(h):
        for j in range(w):
            if a[i][j]==-1:
                continue
            check[a[i][j]]+=1
    ans=0
    for i in range(10):
        ans += pre[i]*check[i]
    print(ans)

def main(): 
    warshall_floyd()

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    h,w=map(int,input().split())
    C=[list(map(int,input().split())) for _ in range(10)]

    # Warshall-Floyd
    from itertools import product
    for k,i,j in product(range(10),repeat=3):
        C[i][j]=min(C[i][j],C[i][k]+C[k][j])

    # input
    A=[list(map(int,input().split())) for _ in range(h)]

    ans=0
    for i,j in product(range(h),range(w)):
        a=A[i][j]
        if(a==-1): continue
        ans+=C[a][1]
    print(ans)
resolve()

Submission status: Accepted

Solution code:
from sys import stdin

inf = 10**10

h,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(10)]

lin = [list(map(int,stdin.readline().rstrip().split())) for _ in range(h)]

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    #k：中継
    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

li = warshall_floyd(li)
liv = []
for i in range(10):
    liv.append(li[i][1])

point = 0
for i in range(h):
    for j in range(w):
        if lin[i][j] == -1:
            continue
        point += liv[lin[i][j]]

print(point)

Submission status: Accepted

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

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

ans = 0
for h in range(H):
    for w in range(W):
        if AAA[h][w] != -1:
            ans += ccc[AAA[h][w]][1]

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

INF = 1000000


def main():
    H, W = map(int, input().split())
    adj_matrix = [[int(c) for c in input().split()] for i in range(10)]
    
    A = [[int(c) for c in input().split()] for i in range(H)]

    def solve(now, S, dp):
        if now == 1:
            dp[now][S] = 0
            return dp[now][S]
        elif dp[now][S] != INF:
            # 訪問済み
            return dp[now][S]
        else:
            res = INF
            for i in range(10):
                if i == now:
                    continue
                if not (S >> i & 1):
                    res = min(res, solve(i, S | (1 << i), dp) + adj_matrix[now][i])
            dp[now][S] = res
            return dp[now][S]

    minimum_distance = {}
    for i in range(10):
        dp = [[INF for c in range(1 << 10)] for i in range(10)]
        minimum_distance[i] = solve(i, 1 << i, dp)

    wall_num = {i: 0 for i in range(10)}
    for line_ in A:
        for value_ in line_:
            if value_ == -1:
                continue
            else:
                wall_num[value_] += 1
    ans = 0
    for i in range(10):
        ans += wall_num[i] * minimum_distance[i]
    print(ans)

    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, input().split())
    cost = 0
    digit = []
    for i in range(10):
        digit.append([])
        a = [int(i) for i in input().split()]
        digit[i] = a

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

    for i in range(H):
        A = [int(i) for i in input().split()]
        for j in range(W):
            if A[j] >= 0:
                cost += digit[A[j]][1]
    print(cost)
    




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def dijkstra_heap(n,s,edge):
    # 始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n  # True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heappush(edgelist, e)
    while len(edgelist):
        minedge = heappop(edgelist)
        # まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heappush(edgelist, [e[0] + d[v], e[1]])
    return d
def examD():
    H, W = LI()
    c = [LI() for _ in range(10)]
    A = [LI() for _ in range(H)]
    edge = [[] for i in range(10)]
    # edge[i] : iから出る道の[重み,行先]の配列
    for i in range(10):
        for j in range(10):
            x, y, z = i, j, c[i][j]
            edge[x].append([z, y])
    res = []
    for i in range(10):
        res.append(dijkstra_heap(10, i, edge))
#    print(res)
    d = defaultdict(int)
    for l in A:
        for j in l:
            d[j] +=1
    ans = 0
    for i in range(10):
        ans += d[i]*res[i][1]
    print(ans)

import sys,copy,bisect,itertools
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, atan2
from operator import mul
from functools import reduce
sys.setrecursionlimit(10 ** 9)

INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7



def dijkstra(G, s=0):
    n = len(G)
    que = [(0, s)]
    dist = [INF] * n
    dist[s] = 0
    while que:
        min_dist, u = heappop(que)
        if min_dist > dist[u]:
            continue
        for v, c in enumerate(G[u]):
            if dist[u] + c < dist[v]:
                dist[v] = dist[u] + c
                heappush(que, (dist[u] + c, v))
    return dist


h, w = LI()
G = LIR(10)
G = [i for i in zip(*G)]
dist = dijkstra(G, 1)
A = LIR(h)
ret = 0
for y in range(h):
    for x in range(w):
        if A[y][x] != -1:
            ret += dist[A[y][x]]


print(ret)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
C = []
V = 10
ctr = [0 for _ in range(V)]

for _ in range(V):
	C.append(list(map(int, input().split())))
	
for _ in range(H):
	A = list(map(int, input().split()))
	for i in range(W):
		if A[i] != -1:
			ctr[A[i]] += 1
			
for k in range(V):
	for i in range(V):
		for j in range(V):
			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(V):
	ans += ctr[i] * C[i][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):
            x = C[i][k] + C[k][j]
            if x < C[i][j]:
                C[i][j] = x

answer = 0
for x in A:
    for y in x:
        if y >= 0:
            answer += C[y][1]
print(answer)

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)]
res = 0
for k in range(10):
  for i in range(10):
    for j in range(10):
      c[i][j] = min(c[i][k] + c[k][j], c[i][j])
for y in range(H):
  for x in range(W):
    if (a[y][x] != -1) or (a[y][x] == 1):
      res += c[a[y][x]][1]
print(res)

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
ans = 0
H, W = map(int, input().split())
c = []
for i in range(10):
    tc = list(map(int, input().split()))
    c.append(tc)
c = np.array(c)
short = shortest_path(c)
# print(shortest_path(c))
A = []
for i in range(H):
    ta = list(map(int, input().split()))
    A.append(ta)
    for j in ta:
        if j != -1:
            ans += short[j][1]
            # print(ans)
print(int(ans))

Submission status: Accepted

Solution code:
H,W = [int(i) for i in input().split(' ')]
C = [[int(i) for i in input().split(' ')]for _ in range(10)]
 
prev = [-1]*10
row = [int(i) for i in range(10)]
ansewrDict = {}
total = 0

for v in row:
    ansewr = {str(i): 1000 for i in range(10)}
    d = {str(i) : 1000 for i in range(10)}
    if v == -1:
        continue
    s = v
    d[str(s)] = 0
    
    while d:
        u = min(d, key=d.get)
        ansewr[u] = d.pop(u)

        for i in range(10):
            if ansewr[str(i)] > ansewr[u] + C[int(u)][i]:
                d[str(i)] = ansewr[u] + C[int(u)][i]
                ansewr[str(i)] = ansewr[u] + C[int(u)][i]
    
    ansewrDict[str(v)] = ansewr

for _ in range(H):
    row = input().split(' ')
    for v in row:
        if v == '1' or v == '-1':
            continue
        
        total += ansewrDict[v]['1']
print(total)

Submission status: Accepted

Solution code:
H,W = map(int, input().split())
C = [[int(c) for c in input().split()] for _ in range(10)]
A = [[int(a) for a in input().split()] for _ 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:
# coding: utf-8
# Your code here!
import collections

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

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

cost=[[0]*10 for _ in range(10)]

dp=[table[i][1] for i in range(10)]

#print(dp)
for n in range(10):
    temp=dp[:]
    for i in range(10):
        for j in range(10):
            temp[i]=min(table[i][j]+dp[j] if j!=i else temp[i],temp[i])
    dp=temp[:]
#print(dp)

c=collections.Counter("")
for _ in range(H):
    c+=collections.Counter(list(map(int,input().split())))

#print(c)
ans=0
for item in c.items():
    if item[0]==-1:
        continue
    else:
        ans+=dp[item[0]]*item[1]

print(ans)

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
######################################################
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
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)]
mod = 10**9 + 7
inf = float('inf')
ans = int(0)
H, W = LI()
c = [LI() for _ in range(10)]
A = [LI() for _ in range(H)]
d = [[float("inf") for i in range(10)] for i in range(10)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(10):
    for j in range(10):
        d[i][j] = c[i][j]
for i in range(10):
    d[i][i] = 0 #自身のところに行くコストは０
#print(warshall_floyd(10,d))
L = warshall_floyd(10,d)
cur = int(0)
for i in range(H):
    for j in range(W):
        l = A[i][j]
        if l>=0:
            cur += L[l][1]

ans = cur
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

H,W=map(int, sys.stdin.readline().split())
dp=[ [ float("inf") for j in range(10) ] for i in range(10) ]

for i in range(10):
    c=map(int, sys.stdin.readline().split())
    for j,x in enumerate(c):
        dp[i][j]=x


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


ans=0
for _ in range(H):
    A=map(int, sys.stdin.readline().split())
    for a in A:
        if a==-1: continue
        ans+=dp[a][1]

print ans

Submission status: Accepted

Solution code:
# ワーシャルフロイド
def warshall_floyd(n, d):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i] + d[i][k])


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

N = 10
d = [None] * N
for i in range(N):
    d[i] = list(map(int, input().split()))
warshall_floyd(N, d)

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

Submission status: Accepted

Solution code:
# ワーシャルフロイド
def warshall_floyd(n, d):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i] + d[i][k])


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

N = 10
d = [None] * N
for i in range(N):
    d[i] = list(map(int, input().split()))
warshall_floyd(N, d)

m = [d[i][1] for i in range(N)]

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

Submission status: Accepted

Solution code:
# ワーシャルフロイド
def warshall_floyd(n, d):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i] + d[i][k])


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

N = 10
d = [None] * N
for i in range(N):
    d[i] = list(map(int, input().split()))
warshall_floyd(N, d)

m = [d[i][1] for i in range(N)]

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
c = [list(map(int, input().split())) for i in range(10)]
A = []
for i in range(H):
    A.extend(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 Ai in A:
    if Ai != -1:
        ans += c[Ai][1]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

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

C_new = np.where(C == 0, 10**9, C)
G = csgraph_from_dense(C_new, null_value=10**9)
d = floyd_warshall(G)

ans = 0
for line in A:
  for i in line:
    if i != -1:
      ans += d[i, 1]
      
print(int(ans))

Submission status: Accepted

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

A=[]
for i in range(H):
    A+=list(map(int,input().split()))
A.sort()
while A[0]==-1:
    A.pop(0)

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

True_Map = warshall_floyd(C,10)

ans=0
for i in A:
    ans+=True_Map[i][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)]
lst=[0]*10
for i in range(h):
    for j in range(w):
        A=a[i][j]
        if A!=-1:
            lst[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])
lst[1]=0
ans=0
for i in range(10):
    ans+=c[i][1]*lst[i]
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
dist = [list(map(int, input().split())) for _ in range(10)]
n = len(dist)
for k in range(n):
  for i in range(n):
    for j in range(n):
      if dist[i][j] > dist[i][k] + dist[k][j]:
        dist[i][j] = dist[i][k] + dist[k][j]       
list_a = [list(map(int, input().split())) for _ in range(h)]
result = 0
for one_row in list_a:
  for one_a in one_row:
    if one_a != -1:
      result += dist[one_a][1]
print(result)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import numpy as np
from scipy.sparse.csgraph import shortest_path

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

c_table = []

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

a_table = []

for _ in range(H):
    a_table.append(list(map(int, input().split())))

c_table = np.array(c_table)
a_table = np.array(a_table)

d_matrix = shortest_path(c_table)
cost = 0

for h in range(H):
    a_list = a_table[h]
    for a in a_list:
        if a == -1:
            continue
        cost += d_matrix[a][1]

ans = int(cost)
print(ans)

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
cost = [[int(i) for i in input().split()] for j in range(10)]
ans = 0
for k in range(10):
    for i in range(10):
        for j in range(10):
            if cost[i][k] < 10000 and cost[k][j] < 10000:
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
for i in range(a):
  for j in input().split():
    j = int(j)
    if j == 0 or 2 <= j <= 9:
      ans += cost[j][1]
print(ans)

Submission status: Accepted

Solution code:
import copy
H,W=map(int,input().split())
C=[list(map(int,input().split()))for _ in range(10)]
A=[list(map(int,input().split()))for _ in range(H)]
d=copy.deepcopy(C)
for k in range(10):
    for i in range(10):
        for j in range(10):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
ans=0
for al in A:
    for a in al:
        if a!=-1:
            ans+=d[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())))
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):
    s=list(map(int,input().split()))
    for j in s:
        if j!=1 and j!=-1:
            ans+=c[j][1]
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
mat=[]
for i in range(10):
    mat.append([int(i) for i in input().split()])

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

ans=0
for i in range(n):
    l=[int(x) for x in input().split()]
    for z in l:
        if z!=-1 and z!=1:
           # print(z)
            ans+=mat[z][1]
print(ans)

Submission status: Accepted

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

for i in range(10):
    cst.append(list(map(int,input().split())))

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

li = [10**4 for i in range(10)] 
li[1] = 0

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

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

print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
C=[1001]*10
C[1]=0

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

for _ in range(10):
  for i in range(10):
    if i!=1:
      for j in range(10):
        if i!=j:
          if C[i]>c[i][j]+C[j]:
            C[i]=c[i][j]+C[j]
          
ans=0        
for i in range(H):
  for j in list(map(int,input().split())):
    if j!=-1:
      ans+=C[j]
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
INF=float('inf')
cost=[[INF]*10 for _ in range(10)]
for i in range(10):
  tmp=list(map(int,input().split()))
  for j in range(10):
    cost[i][j]=tmp[j]
def warshal_floyd(cost):
  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])
  return cost
ans=0
min_cost=warshal_floyd(cost)
for i in range(H):
  tmp=list(map(int,input().split()))
  for j in range(W):
    if tmp[j]==-1 or tmp[j]==1:
      pass
    else:
      ans+=min_cost[tmp[j]][1]                 
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall

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

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

wall = []

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

#solve
#1へのコスト
costone = [(10**3) + 1 for i in range(11)]
#-1, 1はコストがかからないため０で初期化
costone[1] = 0
#-1の処理
costone[10] = 0
#ワーシャルフロイド法を使う
#iは出発、jは経由,
c = floyd_warshall(c)
##for i in range(10):
##    for j in range(10):
##        for k in range(10):
##            c[i][k] = min(c[i][k], c[i][j] + c[j][k])
#costoneを更新
for i in range(10):
    costone[i] = min(costone[i], c[i][1])
sum = 0


for i in range(h):
    for j in range(w):
        sum += costone[wall[i][j]]
print(int(sum))

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
n = 10
g = [None] * n
for i in range(n):
    g[i] = list(map(int, input().split()))

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

cost = warshall_floyd(g, n)
ans = 0
for _ in range(h):
    for w in list(map(int, input().split())):
        if w == -1: continue
        ans += cost[w][1]
print(ans)

Submission status: Accepted

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


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

N = 10
d = [None] * N
for i in range(N):
    d[i] = list(map(int, input().split()))

warshall_floyd(N, d)

c = {i: 0 for i in range(N)}
for i in range(H):
    for j in map(int, input().split()):
        if j == -1:
            continue
        c[j] += 1

print(sum(c[i] * d[i][1] for i in range(N)))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

h,w = inpl()
wall = []
mask = [] 
res = 0
for i in range(10):
    mask.append(inpl())
for y in range(h):
    wall.append(inpl())
for k in range(10):
    for i in range(10):
        for j in range(10):
            mask[i][j] = min(mask[i][j], mask[i][k] + mask[k][j])
for i in range(h):
    for j in range(w):
        tmp = wall[i][j]
        if abs(tmp) == 1:
            continue
        res += mask[tmp][1]
print(res)

Submission status: Accepted

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

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

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

ans = 0
A = [list(map(int, input().split())) for _ in range(h)]

for i in range(h):
    for j in range(w):
        if A[i][j] not in [-1,1]:
            ans += dp[A[i][j]][1]

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    H,_ = map(int,input().split())
    DP = [[2 ** 63 - 1 for _ in range(10)] for _ in range(10)]
    for i in range(10):
        DP[i] = list(map(int,input().split()))

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

    import collections
    import itertools
    A = [list(map(int,input().split())) for _ in range(H)]
    c = collections.Counter(itertools.chain.from_iterable(A))
    ans = 0
    for i in range(10):
        ans += c[i] * DP[i][1] 
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)

def main():
    h, w = map(int, input().strip().split())
    c = [[0] * 10 for _ in range(10)]
    for i in range(10):
        c[i] = list(map(int, input().strip().split()))
    a = [[0] * w for _ in range(h)]
    for i in range(h):
        a[i] = list(map(int, input().strip().split()))

    ary = list(c)
    for k in range(10):
        for i in range(10):
            for j in range(10):
                ary[i][j] = min(ary[i][j], ary[i][k] + ary[k][j])
    ans = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] not in (-1, 1):
                # print(ary[i][j])
                ans += ary[a[i][j]][1]
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

cost = floyd_warshall(c)
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:
H,W=map(int,input().split())

co=[]
c=[0]*10
for i in range(10):
   temp=list(map(int,input().split()))
   co.append(temp)


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

for i in range(10):
    c[i]=co[i][1]


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