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, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from heapq import heappop, heappush

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist


H, W = MAP()
C = [LIST() for i in range(10)]
A = [LIST() for i in range(H)]

graph = defaultdict(list)

for i in range(10):
    for j in range(10):
        cost = C[i][j]
        graph[i].append((j, cost))

ans = 0
for i in range(H):
    for j in range(W):
        from_num = A[i][j]
        if from_num == -1:
            continue
        elif from_num == 1:
            continue
        else:
            ans += dijkstra(graph, from_num)[1]
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
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
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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
cost = [LIST() for _ in range(10)]
wall = [LIST() for _ in range(H)]

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

magic = 0
for i in range(H):
	for j in range(W):
		if wall[i][j] == -1:
			pass
		else:
			magic += cost[wall[i][j]][1]

print(magic)

Submission status: Accepted

Solution code:
'''
https://atcoder.jp/contests/abc079/tasks/abc079_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

    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)]
    N = 10
    for k in range(N):
        for i in range(N):
            for j in range(N):
                c[i][j] = min(c[i][j], c[i][k]+c[k][j])
    res = 0
    for i in A:
        for j in i:
            if j == -1:
                continue
            res += c[j][1]
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(10)]
for i in range(10):
    for j in range(10):
        for k in range(10):
            magic[j][k] = min(magic[j][k], magic[j][i]+magic[i][k])

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()

from scipy.sparse.csgraph import floyd_warshall
h,w=map(int,input().split())
table=[]
for i in range(10):
  table.append([int(i) for i in input().split()])
d=floyd_warshall(csgraph=table, directed=True, return_predecessors=False)

ans=0
for i in range(h):
  A=[int(i) for i in input().split()]
  for a in A:
    if a==-1:
      continue
    else:
      ans+=d[a][1]
print(int(ans))

Submission status: Accepted

Solution code:
import numpy as np
H, W = map(int, input().split())

c = []
for _ in range(10):
    tmp = list(map(int, input().split()))
    c.append(tmp)
c = np.array(c)
# print(c)

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


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


def main():
    H, W = MI()
    N = 10
    d = [None for i in range(N)]
    A = [None] * H

    for i in range(N):
        d[i] = LI()

    for i in range(H):
        A[i] = LI()

    d = warshall_floyd(d, N)

    # print_matrix(d)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
inf = float("inf")
H, W = map(int, input().split())
graph = np.array([list(map(int, input().split())) for _ in range(10)])

shortest_paths = shortest_path(csr_matrix(graph), method="D")
ans = 0

Alist = [list(map(int, input().split())) for _ in range(H)]
for line in Alist:
    for a in line:
        if a >= 0:
            ans += shortest_paths[a][1]
print(int(ans))

Submission status: Accepted

Solution code:
import math,itertools,bisect,sys,copy,queue

def LI(): return [int(x) for x in sys.stdin.readline().split()]

H,W = LI()
C = [LI() for _ in range(10)]
A = [LI() 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 x in range(W):
    for y in range(H):
        if A[y][x] >= 0:
            ans += C[A[y][x]][1]
print (ans)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
c = [0]*10
for i in range(10):
  c[i] = [int(x) for x in 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):
  a = [int(x) for x in input().split()]
  for j in range(w):
    if a[j] == -1:
      continue
    else:
      ans += c[a[j]][1]

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
c = [0]*10
for i in range(10):
  c[i] = [int(x) for x in 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]])

ans = 0
for i in range(h):
  a = [int(x) for x in input().split()]
  for j in range(w):
    if a[j] == -1:
      continue
    else:
      ans += c[a[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:
            ans += C[A[i][j]][1]

print(ans)

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

INF = 10*10

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

N = 100

# mp[i][j]..i→1にj回でする時の最小魔力
mp = [[INF]*N for _ in range(11)]
mp[0][1] = 0
for i in range(10):
    mp[i][1] = C[i][1]

for j in range(2,N):
    for i in range(10):
        mp[i][j] = min((C[i][k] + mp[k][j-1]) for k in range(10))

cnt = [0]*10
for a in A:
    for i in range(10):
        cnt[i] += a.count(i)

ans = 0
for i in range(10):
    ans += cnt[i] * mp[i][N-1]

print(ans)

Submission status: Accepted

Solution code:
INFTY = 10**5
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)]
dist = [[INFTY for _ in range(10)] for _ in range(10)]
for i in range(10):
    dist[i][i] = 0
for i in range(10):
    for j in range(10):
        dist[i][j] = C[i][j]
for k in range(10):
    for i in range(10):
        for j in range(10):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
cnt = 0
for i in range(H):
    for j in range(W):
        a = A[i][j]
        if a!=-1:
            cnt += dist[a][1]
print(cnt)

Submission status: Accepted

Solution code:
INF = 100000

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

dist = [[INF for j in range(10)] for i in range(10)]

for i in range(10):
    for j in range(10):
        dist[i][j] = C[i][j]

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

ans = 0

for al in A:
    for a in al:
        if a != -1:
            ans += dist[a][1]

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
H,W = [int(x) for x in stdin.readline().rstrip().split()]
cost = []
for i in range(10):
    cost.append([int(x) for x in stdin.readline().rstrip().split()])

A = []
for i in range(H):
    A.append([int(x) for x in stdin.readline().rstrip().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])

ans = 0
for a in A:
    for aa in a:
        if aa == -1:
           continue
        ans += cost[aa][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:
			continue
		else:
			ans += C[A[i][j]][1]

print(ans)

Submission status: Accepted

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

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

    return d #d[i][j]に頂点i, j間の最短距離を格納

def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):
    min_cost = warshall_floyd(c,10)
    answer = 0

    for h in range(H):
        for w in range(W):
            if A[h][w] == -1:
                continue

            answer += min_cost[A[h][w]][1]
    print(answer)
    return


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]]"
    solve(H, W, c, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import heapq
import bisect
from scipy.sparse.csgraph import shortest_path
import numpy as np

MOD = float('inf')
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

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

result = shortest_path(np.array(c))

ans = 0
for i in range(H):
    for l in range(W):
        if A[i][l] != -1:
            ans += result[A[i][l]][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=[list(map(int,input().split())) for i in range(H)]

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

Submission status: Accepted

Solution code:
import sys
from pprint import pprint

def warshall_floyd(d, n):
    #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])
    has_nagative_cycle = False
    for i in range(n):
        if d[i][i] < 0:
            has_nagative_cycle = True
            break
    for i in range(n):
        d[i][i] = 0
    return has_nagative_cycle

H, W = map(int, sys.stdin.readline().strip().split())
numbers = [[] for _ in range(10)]
for i in range(10):
	numbers[i] = list(map(int, sys.stdin.readline().strip().split()))

walls = [[] for _ in range(H)]
for i in range(H):
	walls[i] = list(map(int, sys.stdin.readline().strip().split()))

warshall_floyd(numbers, 10)
# pprint(numbers)

ans = 0
for h in range(H):
	for w in range(W):
		n = walls[h][w]
		ans += 0 if n == -1 or n == 1 else numbers[n][1]
		# print(n, numbers[n][1])

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(10)]
cnt = [0]*11
for _ in range(H):
  for a in map(int, input().split()):
    cnt[a] += 1
D = [[C[i][j] for j in range(10)] for i in range(10)]
k = 0
while k < 10:
  i = 0
  while i < 10:
    j = 0
    while j < 10:
      D[i][j] = min(D[i][j], D[i][k]+D[k][j])
      j += 1
    i += 1
  k += 1
print(sum([cnt[i]*D[i][1] for i in range(10)]))