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: Wrong Answer

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: Wrong Answer

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(1,n+1):
        for i in range(1,n+1):
            for j in range(1,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: Wrong Answer

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)
print(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: Wrong Answer

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])
            ma[i][j] = min(ma[i][j], ma[i][k]+ma[k][j])
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: Wrong Answer

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[i][j] = min(ma[i][j], ma[i][k]+ma[k][j])
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: Wrong Answer

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[i][j] = min(ma[i][j], ma[i][k]+ma[k][j])
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: Wrong Answer

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=0).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: Wrong Answer

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 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])
    #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: Wrong Answer

Solution code:
import numpy as np
import scipy.sparse.csgraph as csg

from copy import deepcopy

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

d = csg.floyd_warshall(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 i in range(h):
    for j in range(w):
        if a[i][j] != -1:
            ans += d[a[i][j]][1]

print(ans)

Submission status: Wrong Answer

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

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])
res=0

for i in range(H):
    for j in range(W):
        a=A[i][j]
        res+=c[a][1]

print(res)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
    h, w = map(int, input().split())
    c = [[int(i) for i 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])
    print(sum(c[k][1] * v for k, v in Counter(sum([[int(i) for i in input().split() if i != "-1"] for _ in range(h)], [])).items()))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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


# 数字->数字に変えるcostを更新する（ワーシャルフロイド法）
for i in range(10):
    for j in range(10):
        for k in range(10):
            Cs[i][j] = min(Cs[i][j], Cs[i][k] + Cs[k][j])

# 解答
count = 0
for i in range(H):
    for j in range(W):
        if As[i][j] >= 0:
            #print('number=', As[i][j], 'cost=', Cs[As[i][j]][1])
            count += Cs[As[i][j]][1]

print(count)

Submission status: Wrong Answer

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

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


# 数字->数字に変えるcostを更新する（ワーシャルフロイド法）
for i in range(10):
    for j in range(10):
        for k in range(10):
            Cs[i][j] = min(Cs[i][j], Cs[i][k] + Cs[k][j])

# 解答
count = 0
for i in range(H):
    for j in range(W):
        if As[i][j] > 0:
            #print('number=', As[i][j], 'cost=', Cs[As[i][j]][1])
            count += Cs[As[i][j]][1]

print(count)

Submission status: Wrong Answer

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

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


# 数字->数字に変えるcostを更新する（ワーシャルフロイド法）
for i in range(10):
    for j in range(10):
        for k in range(10):
            Cs[i][j] = min(Cs[i][j], Cs[i][k] + Cs[k][j])

# 解答
count = 0
for i in range(H):
    for j in range(W):
        if As[i][j] != -1 and As[i][j] != 1:
            #print('number=', As[i][j], 'cost=', Cs[As[i][j]][1])
            count += Cs[As[i][j]][1]

print(count)

Submission status: Wrong Answer

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

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


# 各数字から1に変えるcostを求める
# ワーシャルフロイド法
for i in range(10):
    for j in range(10):
        for k in range(10):
            Cs[i][j] = min(Cs[i][j], Cs[i][k] + Cs[k][j])


# 解答
count = 0
for i in range(H):
    for j in range(W):
        if As[i][j] != -1 and As[i][j] != 1:
            #print('number=', As[i][j], 'cost=', Cs[As[i][j]][1])
            count += Cs[As[i][j]][1]

print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import deque
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 funci(d,j):
    ret=0
    for i in range(len(d)-1):
        ret+=c[d[i]][d[i+1]]
    ret+=c[d[-1]][j]
    return ret

def bfs(i):#i!=1,i->1 minimum
    b=c
    ret=b[i][1]
    todo=deque([[i,j] for j in range(10) if j!=i])
    while len(todo)>0:
        d=todo.popleft()
        ret=min(ret,funci(d,1))
        for i in [j for j in range(10) if j not in d and j!=1]:
            f=d
            if funci(f,i)<ret:
                f.append(i)
                todo.append(f)
    return ret
g=[bfs(i)for i in range(10)]
ans=0
for ai in a:
    for aij in ai:
        ans+=g[aij] if aij != -1 else 0
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
wlist=[[0]*10 for _  in range(10)]
for i in range(10):
    b=list(map(int,input().split()))
    for j in range(10):
        wlist[i][j]=b[j]
for i in range(10):
    for j in range(10):
        for k in range(10):
            wlist[i][j]=min(wlist[i][j],wlist[i][k]+wlist[k][j])
ans=0
for _ in range(h):
    t=list(map(int,input().split()))
    for i in t:
        if i==-1 or i==1:
            continue
        else:
            ans+=wlist[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
wlist=[[0]*10 for _  in range(10)]
for i in range(10):
    b=list(map(int,input().split()))
    for j in range(10):
        wlist[i][j]=b[j]
for i in range(10):
    for j in range(10):
        for k in range(10):
            wlist[i][k]=min(wlist[i][k],wlist[i][j]+wlist[j][k])
ans=0
for _ in range(h):
    t=list(map(int,input().split()))
    for i in t:
        if i==-1 or i==1:
            continue
        else:
            ans+=wlist[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
def dijkstra(s,n,cost):
  d=[float('inf')]*n
  visited=[0]*n
  d[s]=0
  while True:
    v=-1
    for i in range(n-1,-1,-1):
      if visited[i]==0 and v==-1:
        v=i
      elif visited[i]==0 and d[i]<d[v]:
        v=i
    if v==-1:
      break
    visited[v]=1
    for j in range(n-1,-1,-1):
      d[j]=min(d[j],d[v]+cost[j][v])
  return d

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

Submission status: Wrong Answer

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

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

converted = sum([wf[board[h][w]][1] if board[h][w] >= 0 else 0 for w in range(W) for h in range(H)])

print(converted)

Submission status: Wrong Answer

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

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

converted = sum([wf[board[h][w]][1] if board[h][w] > 0 else 0 for w in range(W) for h in range(H)])

print(converted)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

to_be_changed = []
# MAP = [list(map(int, input().split())) for _ in range(H)]
for _ in range(H):
    row = list(map(int, input().split()))
    for v in row:
        if v >= 2:
            to_be_changed.append(v)
# print(to_be_changed)


# compute distance from i to j: Floyd Warshall
dist = defaultdict(lambda: defaultdict(lambda: float('inf')))
N = 10
for u in range(N):
    dist[u][u] = 0
for u in range(N):
    for v in range(N):
        if u != v:
            dist[u][v] = min(dist[u][v], c[u][v])

for w in range(N):
    for u in range(N):
        for v in range(N):
            if dist[u][v] > dist[u][w] + dist[w][v]:
                dist[u][v] = dist[u][w] + dist[w][v]

cost = sum(dist[u][1] for u in to_be_changed)
print(cost)

Submission status: Wrong Answer

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(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
magic = [[0 for i in range(10)] for j in range(10)]
Wall = []
min_magic = [10000 for k in range(10)]
min_magic_num = [0 for l in range(10)]


for i in range(10):
    magic[i] = list(map(int, input().split()))
    for j in range(1, 10):
        if (i != j) and (magic[i][j] < min_magic[i]):
            min_magic[i] = magic[i][j]
            min_magic_num[i] = j
    if (i != 0) and (magic[i][0] < min_magic[0]):
        min_magic[i] = magic[i][0]
        min_magic_num[i] = 0

for j in range(H):
    Wall.extend(list(map(int, input().split())))
Wall_number = [0 for i in range(10)]
for i in range(10):
    Wall_number[i] = Wall.count(i)

def clear_wall(num, goal):
    if num == -1 or num == goal:
        return 0
    elif min_magic_num[num] == goal:
        return min_magic[num]
    else:
        ans = magic[num][goal]
        for i in range(10):
            ans = min(ans, magic[num][i] + magic[i][goal])
        return ans
for i in range(10):
    for j in range(10):
        magic[i][j] = clear_wall(i, j)

answer = 0
for i in range(10):
    if Wall_number[i] == 0:
        continue
    else:
        answer += Wall_number[i] * magic[i][1]
print(answer)

Submission status: Wrong Answer

Solution code:

url = "https://atcoder.jp//contests/abc079/tasks/abc079_d"

def main():
    H, W = list(map(int, input().split()))
    mp_lis = []
    for i in range(10):
        mp_lis.append(list(map(int, input().split())))
    min_mp = []
    for i in range(10):
        direct = mp_lis[i][1]
        X = i
        tmp_mp = 0
        while X != 1:
            t = sorted(mp_lis[X])
            tmp_mp += t[1] # 0 以外の最小値を格納
            X = mp_lis[X].index(t[1]) # 変換後の数字のインデックス格納
            if tmp_mp >= direct:
                break
        min_mp.append(min(direct, tmp_mp))
    mp = 0
    for i in range(H):
        masu = list(map(int, input().split()))
        for m in masu:
            if m == -1:
                continue
            mp += min_mp[m]
    print(mp)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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(ans)

Submission status: Wrong Answer

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 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: Wrong Answer

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(1):
    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: Wrong Answer

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(int(ans))

Submission status: Wrong Answer

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 += C[A[i][j]][1]
print(int(ans))

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra, 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 = dijkstra(G)

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

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra, 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 = dijkstra(G)

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

H, W = mi()
C = li2(10)
A = li2(H)

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

## 各要素における最小コストを合計
ans = 0
for i in range(H):
    for j in range(W):
        if abs(A[i][j]) != 1:
            ans += C[A[i][j]][1]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

H, W = mi()
C = li2(10)
A = li2(H)

## ワーシャルフロイド法
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):
    for j in range(W):
        if abs(A[i][j]) != 1:
            ans += C[A[i][j]][1]

print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
C = [list(map(int, input().split())) for j in range(10)]
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])

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

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
C = [list(map(int, input().split())) for j in range(10)]
for i in range(10):
    for j in range(10):
        for k in range(10):
            if C[i][k] > C[i][j] + C[j][k]:
                C[i][k] = C[i][j] + C[j][k]
S = 0
for i in range(H):
    for x in list(map(int, input().split())):
        if x != -1:
            S += C[x][1]
print(S)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
C = [list(map(int, input().split())) for j in range(10)]
for i in range(10):
    for j in range(10):
        for k in range(10):
            if C[i][k] > C[i][j] + C[j][k]:
                C[i][k] = C[i][j] + C[j][k]
S = 0
for i in range(H):
    for x in list(map(int, input().split())):
        if x == -1:
            continue
        S += C[x][1]
print(S)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
C = [list(map(int, input().split())) for j in range(10)]
for i in range(10):
    for j in range(10):
        for k in range(10):
            if C[i][k] > C[i][j] + C[j][k]:
                C[i][k] = C[i][j] + C[j][k]
S = 0
for i in range(H):
    for x in map(int, list(input().split())):
        if x == -1:
            continue
        S += C[x][1]
print(S)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
C = [list(map(int, input().split())) for j in range(10)]
for i in range(10):
    for j in range(10):
        for k in range(10):
            if C[i][k] > C[i][j] + C[j][k]:
                C[i][k] = C[i][j] + C[j][k]
S = 0
for i in range(H):
    for x in map(int, input().split()):
        if x == -1:
            continue
        S += C[x][1]
print(S)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
H, W = map(int,input().split())
min_cost = [float("inf")] * 10
min_cost[1] = 0
costs = [list(map(int,input().split())) for _ in range(10)]
que = [(0, 1)]
while que:
    cost, v = heappop(que)
    if cost != min_cost[v]:
        continue
    for to in range(10):
        if min_cost[to] > cost + costs[v][to]:
            min_cost[to] = cost + costs[v][to]
            heappush(que, (min_cost[to], to))
ans = 0
for i in range(H):
    for ch in list(map(int,input().split())):
        if ch != -1:
            ans += min_cost[ch]
print(ans)

Submission status: Wrong Answer

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


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

shortest_path = list(zip(*graph))[1]
ans = 0
for _ in range(h):
    for a in map(int, input().split()):
        if a == -1:
            continue
        ans += shortest_path[a]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

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

ctr = Counter(sum(A, []))
ans = 0
for i, c in ctr.items():
    if i == -1:
        continue
    ans += graph[i][1] * c
print(ans)

Submission status: Wrong Answer

Solution code:
def warshall_floyd(c,d):
    #d[i][j]: iからjへの最短距離
    for k in range(10):
        for i in range(10):
            for j in range(10):
              c[j][k] = min(c[j][k],c[j][i] + c[i][k])
              if k == 1:
                  d[j] = c[j][k]
    return d

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_list = [0]*10 
ans = 0
warshall_floyd(c,d_list)

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

Submission status: Wrong Answer

Solution code:
import collections
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 = [0]*10
    
    
def way(n,e,i,p): #現在の数字、現在の必要魔力、始点、暫定最低魔力
    for j in range(0,10):
        if (n == j):
            continue
        if (n == 1):
            if (e < result[i]):
                result[i] = e
            break
        if (e +  c[n][j] < p):
            print(n,e,i,p,j)
            q = e + c[n][j]
            way(j,q,i,p)
        
for i in range(0,10):
    result[i] = c[i][1]
    way(i,0,i,result[i])
    
print(result)

r = []
for w in range(0,10):
    t = 0
    for k in range(0,h):
        l = collections.Counter(a[k])
        t += l[w]
    r.append(t)
print(r)

ans = 0
for z in range(0,10):
    ans += result[z] * r[z]
print (ans)

Submission status: Wrong Answer

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 aa in A:
    for a in aa:
        if a > 1: ans += C[a][1]
print(ans)