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:
from itertools import*
H,W=map(int,input().split())
C=[list(map(int,input().split()))for _ in range(10)]
for i,j,k in product(range(10),repeat=3):C[i][j]=min(C[i][j],C[i][k]+C[k][j])
l=[0]*11
for _ in range(H):
 for i in input().split():l[int(i)]+=1
print(sum(C[i][1]*v for i,v in enumerate(l[:-1])))

Submission status: Wrong Answer

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

import sys
input = sys.stdin.readline

[H,W]= [int(x) for x in input().split()]
c=np.array([[int(x) for x in input().split()] for _ in range(10)])

A=[]
for _ in range(H):
  A+=[int(x) for x in input().split()] 

dd = defaultdict(int)
for key in A:
  if key!=1 and key!=-1:
    dd[key] += 1

res=0
scores=dijkstra(c.T,indices = 1).astype(int)
print(scores)
for k, v in dd.items():
  res+= v*scores[k]
print(res)

Submission status: Wrong Answer

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

import sys
input = sys.stdin.readline

[H,W]= [int(x) for x in input().split()]
c=np.array([[int(x) for x in input().split()] for _ in range(10)])

A=[]
for _ in range(H):
  A+=[int(x) for x in input().split()] 

dd = defaultdict(int)
for key in A:
  if key!=1:
    dd[key] += 1

res=0
for k, v in dd.items():
  res+= v*int(dijkstra(c,indices = k)[1])
print(res)

Submission status: Wrong Answer

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

import sys
input = sys.stdin.readline

[H,W]= [int(x) for x in input().split()]
c=np.array([[int(x) for x in input().split()] for _ in range(10)])

A=[]
for _ in range(H):
  A+=[int(x) for x in input().split()] 

dd = defaultdict(int)
for key in A:
  if key>1:
    dd[key] += 1

res=0
for k, v in dd.items():
  res+= v*int(dijkstra(c,indices = k)[1])
print(res)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")

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)]
# print(c)
# print(a)
cos=[0]*10
for i in range(10):
    cos[i]=c[i][1]
goal=1
li=[i for i in range(10)]
# print(li)
li.remove(1)
for i in range(9):
    tmp=[inf,0]
    for j in li:
        if tmp[0]>c[j][goal]:
            tmp=[c[j][goal],j]
    cos[tmp[1]]=min(cos[tmp[1]],tmp[0]+cos[goal])
    goal=tmp[1]
    li.remove(goal)
    for j in li:
        if cos[i]>cos[goal]+c[i][goal]:
            cos[i]=cos[goal]+c[i][goal]
    # print(cos)
    # print(tmp)
ans=0
for i in range(h):
    for j in range(w):
        if a[i][j]==-1:
            continue
        ans+=cos[a[i][j]]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")

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)]
# print(c)
# print(a)
cos=[0]*10
for i in range(10):
    cos[i]=c[i][1]
goal=1
for i in range(10):
    tmp=[inf,0]
    for j in range(10):
        if j==goal:
            continue
        if tmp[0]>c[j][goal]:
            tmp=[c[j][goal],j]
    cos[tmp[1]]=min(cos[tmp[1]],tmp[0]+cos[goal])
    goal=tmp[1]
    for j in range(10):
        if j==goal:
            continue
        if cos[i]>cos[goal]+c[i][goal]:
            cos[i]=cos[goal]+c[i][goal]
    # print(cos)
    # print(goal)
ans=0
for i in range(h):
    for j in range(w):
        if a[i][j]==-1:
            continue
        ans+=cos[a[i][j]]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
distance=[]
for _ in range(10):
   distance.append(list(map(int,input().split())))

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

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

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

h, w = map(int, input().split())
c = []
a = []
for _ in range(10):
    k = [int(i) for i in input().split()]
    c.append(k)
for _ in range(h):
    a.extend([int(i) for i in input().split()])

count = Counter(a)
c = warshall_floyd(c)
ans = 0
for i in range(2, 10):
    ans += count[i] * c[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

h, w = map(int, input().split())
c = []
a = []
for _ in range(10):
    k = [int(i) for i in input().split()]
    c.append(k)
for _ in range(h):
    a.extend([int(i) for i in input().split()])

count = Counter(a)
c = warshall_floyd(c)
ans = 0
for i in range(2, 10):
    ans += count[i] * c[i][1]
print(ans)

Submission status: Wrong Answer

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

#for k in range(0, 10):
#    print(c[k])
#for k in range(0, 10):
#    print(d[k])
#print(d[8][1])

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

Submission status: Wrong Answer

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# W行H列, x[W][H]
def create_grid(W, H, value = 0):
    return [[ value for _ in range(H)] for _ in range(W)]

########
def warshall_floyd(G):
    # G[i][j]: iからjへの最短距離
    N = len(G)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    return G

if __name__ == "__main__":
    # https://atcoder.jp/contests/abc016/tasks/abc016_3
    H, W = l_inpl()

    # 隣接行列 G, 存在しない辺はINF
    G = []
    for i in range(10):
        l = l_inpl()
        G.append(l)

    
    G = warshall_floyd(G)
    l = []
    for _ in range(H):
        li = l_inpl()
        l.extend(li)
    ans = 0

    for i in range(0, 10):
        if i == 1:
            continue
        ans += G[i][1] * l.count(i)
        print(G[i][1], l.count(i))
    print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def minindex(arrived,costs):
    mindex = "end"
    curmin = 100000000
    for i in range(10):
        if arrived[i]:continue
        if curmin>costs[i]:
            mindex = i
            curmin = costs[i]
    return mindex

H,W = map(int,input().split())
C = [[int(j) for j in input().split()] for i in range(10)]
#C[i][j]はiをjにするコスト
#のつもりなんだけど、ダイクストラ法の逆打ち計算では逆をやります
print(C)

arrived = [False] * 10
arrived[1] = True
Saitan = [None] * 10
Saitan[1] = 0
costs = [1000000] * 10
costs[1] = 0
curpos = 1
print(costs)
for i in range(10):#残り9頂点
    for j,done in enumerate(arrived):
        costs[j] = min(costs[j],costs[curpos] + C[j][curpos])
    if i==9:break
    curpos = minindex(arrived,costs)
    arrived[curpos] = True
A = [[int(i) for i in input().split()] for j in range(H)]

def maryoku(x):
    if x == -1:return(0)
    else:return(costs[x])

print(sum([sum([maryoku(aa) for aa in a]) for a in A]))

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
dist = [[0]*10 for _ in range(10)]
for i in range(10):
    for j, c in enumerate(input().split()):
        dist[i][j] = int(c)
        dist[j][i] = int(c)
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])
count = 0
for _ in range(H):
    for a in input().split():
        if not int(a) == -1:
            count += dist[int(a)][1]
print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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


def f(i, s, m):
    if i == 1:
        return s
    a = float('INF')
    for j, k in enumerate(C[i]):
        if m[j] is True:
            continue
        m[j] = True
        a = min(a, f(j, s + k, m))
        m[j] = False
    return a


def main():
    ans = 0
    for h in range(H):
        for i in A[h]:
            if i > 1:
                m = [False] * 10
                m[i] = True
                ans += f(i, 0, m)
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
c=[list(map(int,input().split())) for i in range(10)]
for i in range(10):
    for j in range(10):
        for k in range(10):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])
for i in range(10):
    for j in range(10):
        for k in range(10):
            c[i][j]=min(c[i][j],c[i][9-k]+c[9-k][j])
l=[]
for i in range(h):
    l.extend(list(map(int,input().split())))
x=0
for i in range(10):
    x+=c[i][1]*l.count(i)
print(x)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
c=[list(map(int,input().split())) for i in range(10)]
for i in range(10):
    for j in range(10):
        for k in range(10):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])
l=[]
for i in range(h):
    l.extend(list(map(int,input().split())))
x=0
for i in range(10):
    x+=c[i][1]*l.count(i)
print(x)

Submission status: Wrong Answer

Solution code:
def sol():
    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)]
    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 i in range(h):
        for j in range(w):
            if a[i][j]==-1: pass
            else: ans+=c[a[i][j]][1]
    print(ans)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
def sol():
    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)]
    d=[1003]*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):
        for j in range(w):
            if a[i][j]==-1: pass
            else: ans+=c[a[i][j]][1]
    print(ans)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
def sol():
    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)]
    d=[1003]*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])
    ans=0
    for i in range(h):
        for j in range(w):
            if a[i][j]==-1: pass
            else: ans+=c[a[i][j]][1]
    print(ans)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
c=[]
for i in range(10):
    l=[int(i) for i in input().split()]
    c.append(l)
a=[]
for i in range(h):
    l=[int(i) for i in input().split()]
    a.append(l)
p=[0]*10
for i in range(10):
    if i==1: continue
    d=[1003]*10
    d[i]=0
    q=set([i])
    while 1:
        if len(q)==0: break
        x=q.pop()
        for j in range(10):
            if i==j: continue
            if (d[j]>d[x]+c[x][j]):
                d[j]=d[x]+c[x][j]
                q.add(j)
    p[i]=d[1]
ans=0
for i in range(h):
    for j in range(w):
        ans+=p[a[i][j]]
print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall
h,w=map(int,input().split())
table=[[0]*10 for i in range(10)]
for i in range(10):
  C=[int(i) for i in input().split()]
  for j in range(10):
    table[i][j]=C[j]
d=floyd_warshall(csgraph=table, directed=True, return_predecessors=False)
print(d)
ans=0
for i in range(h):
  A=[int(i) for i in input().split()]
  for a in A:
    if a!=-1:
      ans+=int(d[a][1])
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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)]
memo = {}
def dfs(nv,vl,cost):
    if nv in memo.keys():
        return memo[nv]
    if nv==1:
        return cost
    vl_ = vl.copy()
    vl_.append(nv)
    ret = []
    for i in range(10):
        if not i in vl_:
            ret.append(dfs(i,vl_,cost+c[nv][i]))
    return min(ret)
cost = []
for i in range(10):
    cost.append(dfs(i,[],0))
    memo[i] = cost[i]
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j]!=-1:
            ans += cost[a[i][j]]
print(ans)

Submission status: Wrong Answer

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

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):
	ans += sum([c[x][1] for x in map(int,input().split()) if x > 1])

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from scipy.sparse.csgraph import floyd_warshall

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

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

A=Counter(A)
print(sum([int(c[i][1] * A[i]) for i in range(2,10) if i in A]))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

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

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

A=Counter(A)
print(sum([c[i][1] * A[i] for i in range(2,10) if i in A]))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

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

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

A=Counter(A)
print(sum([c[i][1] * A[i] for i in range(2,10) if i in A]))

Submission status: Wrong Answer

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)]
INF = float('inf')
cost = 0
D = [[INF]*10 for i in range(10)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            D[i][j] = min(C[i][j],C[i][k]+C[k][j])

for y in range(h):
    for x in range(w):
        if A[y][x] == -1 or A[y][x] == 1:
            continue
        else:
            cost += D[A[y][x]][1]
print(cost)

Submission status: Wrong Answer

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

nums = 10

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

ans = 0
for wi in wall:
  for wij in wi:
    ans += 0 if wij == 0 else cost[wij][1]
    
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = list(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())))


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])
res=0
for i in range(H):
    for j in range(W):
        if(A[i][j]>0):
            res+=c[A[i][j]][1]
print(res)

Submission status: Wrong Answer

Solution code:
def main():
    H, W = map(int, input().split())
    g_list = []
    for i in range(10):
        g_list.append(list(map(int, input().split())))
    min_change = [j[1] for j in g_list]
    flag = [0 for _ in range(10)]
    tep = [(j,g) for j, g in enumerate(min_change) if j != 1]  
    min_g = min(tep, key=lambda a:a[1])[0]
    flag[min_g] = 1
    #print(min_change, flag, min_g)
    while sum(flag) != 9:
        #print(min_change, flag)
        for j in range(10):
            if g_list[j][min_g] + min_change[min_g] < min_change[j]:
                min_change[j] = g_list[j][min_g] + min_change[min_g]
        tep = [(k,g) for k, g in enumerate(min_change) if flag[k] == 0 and k != j and k != 1]
        if tep != []:
            min_g = min(tep, key=lambda a:a[1])[0]
        else :
            break
        flag[min_g] = 1
    s = 0
    for i in range(H):
        wall = list(map(int, input().split()))
        s += sum([min_change[i] for i in wall if i != -1])
    return s
        
if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
def main():
    H, W = map(int, input().split())
    g_list = []
    for i in range(10):
        g_list.append(list(map(int, input().split())))
    min_change = [j[1] for j in g_list]
    flag = [0 for _ in range(10)]
    tep = [(j,g) for j, g in enumerate(min_change) if j != 1]  
    min_g = min(tep, key=lambda a:a[1])[0]
    flag[min_g] = 1
    #print(min_change, flag, min_g)
    while sum(flag) != 9:
        #print(min_change, flag)
        for j in range(10):
            if g_list[j][min_g] + min_change[min_g] < min_change[j]:
                min_change[j] = g_list[j][min_g] + min_change[min_g]
        tep = [(k,g) for k, g in enumerate(min_change) if flag[k] == 0 and k != j]
        if tep != []:
            min_g = min(tep, key=lambda a:a[1])[0]
        else :
            break
        flag[min_g] = 1
    s = 0
    for i in range(H):
        wall = list(map(int, input().split()))
        s += sum([min_change[i] for i in wall if i != -1])
    return s
        
if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
def main():
    H, W = map(int, input().split())
    g_list = []
    for i in range(10):
        g_list.append(list(map(int, input().split())))
    min_change = [j[1] for j in g_list]
    flag = [0 for _ in range(10)]
    tep = [(j,g) for j, g in enumerate(min_change) if j != 1]  
    min_g = min(tep, key=lambda a:a[1])[0]
    flag[min_g] = 1
    #print(min_change, flag, min_g)
    while sum(flag) != 10:
        #print(min_change, flag)
        for j in range(10):
            if g_list[j][min_g] + min_change[min_g] < min_change[j]:
                min_change[j] = g_list[j][min_g] + min_change[min_g]
        tep = [(k,g) for k, g in enumerate(min_change) if flag[k] == 0 and k != j]
        if tep != []:
            min_g = min(tep, key=lambda a:a[1])[0]
        else :
            break
        flag[min_g] = 1
    s = 0
    for i in range(H):
        wall = list(map(int, input().split()))
        s += sum([min_change[i] for i in wall if i != -1])
    return s
        
if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    a,b,c,d = list(map(int, S()))
    s = ["-","+"]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                if eval(str(a)+s[i]+str(b)+s[j]+str(c)+s[k]+str(d)) == 7:
                    print(str(a)+s[i]+str(b)+s[j]+str(c)+s[k]+str(d)+"=7")
                    quit()
#D
def D():
    h,w = LI()
    d = [None for i in range(10)]
    for i in range(10):
        d[i] = LI()
    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):
        s = LI()
        for k in s:
            if k > 0:
                ans += d[k][1]
    print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Wrong Answer

Solution code:
import sys

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = [[int(c) for c in input().split()] for _ in range(10)]
    A = [list(map(int, input().split())) for _ in range(H)]

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

    ans = 0
    for a in A:
        for i in a:
            if i == -1:
                continue
            ans += dp[i][1]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = [[int(c) for c in input().split()] for _ in range(10)]
    A = [list(map(int, input().split())) for _ in range(H)]

    dp = [10**4] * 10
    to1 = []
    for i in range(10):
        to1.append([i, C[i][1]])
    to1 = sorted(to1, key=lambda x: x[1])

    for i in range(10):
        x, y = to1[i]
        dp[x] = y
        for j in range(i):
            xj, _ = to1[j]
            yj = dp[xj] + C[x][xj]
            dp[x] = min(dp[x], yj)

    ans = 0
    for a in A:
        for i in a:
            if i == -1:
                continue
            ans += dp[i]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = [[int(c) for c in input().split()] for _ in range(10)]
    A = [list(map(int, input().split())) for _ in range(H)]

    dp = [10**4] * 10
    to1 = []
    for i in range(10):
        to1.append([i, C[i][1]])
    to1 = sorted(to1, key=lambda x: x[1])

    for i in range(10):
        x, y = to1[i]
        dp[x] = y
        for j in range(i):
            xj, yj = to1[j]
            yj += C[x][xj]
            dp[x] = min(dp[x], yj)

    ans = 0
    for a in A:
        for i in a:
            if i == -1:
                continue
            ans += dp[i]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = [[int(c) for c in input().split()] for _ in range(10)]
    A = [list(map(int, input().split())) for _ in range(H)]

    dp = [0] * 10
    to1 = []
    for i in range(10):
        to1.append([i, C[i][1]])
    to1 = sorted(to1, key=lambda x: x[1])

    for t in to1:
        dp[t[0]] = t[1]

    for i in range(10):
        a = to1[i][0]
        for j in range(i, -1, -1):
            b = to1[j][0]
            dp[a] = min(dp[a], dp[b] + C[a][b])

    ans = 0
    for a in A:
        for i in a:
            if i == -1:
                continue
            ans += dp[i]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def wf(c):
    d = {}
    for i in range(10):
        for j in range(10):
            d[(i,j)] = c[i][j]
    for i in range(10):
        for j in range(10):
            for k in range(10):
                if d[(i,j)] > d[(i,k)] + d[(k,j)]:
                    d[(i,j)] = d[(i,k)] + d[(k,j)]
    e = {}
    for i in range(10):
        e[i] = d[(i,1)]
    return e


def solve(H, W, c, A):
    d = wf(c)
    mp = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] != -1:
                mp += d[A[i][j]]
    return mp


def main():
    H, W = list(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(' '))))

    ans = solve(H, W, c, A)
    print(ans)



if __name__ == '__main__':
    main()