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 collections
import heapq

h, w = map(int, input().split())
cs = [list(map(int, input().split())) for _ in range(10)]
counter = collections.Counter()
for _ in range(h):
    for x in map(int, input().split()):
        if x != -1:
            counter[x] += 1

dists = [float('inf') for i in range(10)]
dists[1] = 0
q = []
for i in range(10):
    heapq.heappush(q, (dists[i], i))

while q:
    d0, i = heapq.heappop(q)
    for j in range(10):
        if j == i:
            continue
        d = d0 + cs[j][i]
        if dists[j] > d:
            dists[j] = d
            heapq.heappush(q, (dists[j], j))

res = 0
for k, v in counter.items():
    res += dists[k] * v
print(res)

Submission status: Accepted

Solution code:
def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges



def main():
    h,w = map(int,input().split())
    ls = [[int(x) for x in input().split()] for _ in range(10)]
    a = [[int(x) for x in input().split()] for _ in range(h)]
    ls = Warshall_Floyd(ls,10)
    cost = []

    for i in range(10):
        cost.append(ls[i][1])
    ans = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] == -1:
                pass
            else:
                ans += cost[a[i][j]]
    print(ans)

if __name__ == "__main__":
    main()

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])
#print(c)

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

Submission status: Accepted

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

for k in range(10):
  for i in range(10):
    for j in range(10):
      costs[i][j] = min(costs[i][j], costs[i][k]+costs[k][j])
ans = 0
for h in range(H):
  for w in range(W):
    if walls[h][w] == -1:
      continue
    else:
      ans += costs[walls[h][w]][1]
print(ans)

Submission status: Accepted

Solution code:
import collections

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

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

route={i:10**3 for i in range(10)}
route[1]=0
nonFixPosi=set([0,2,3,4,5,6,7,8,9])
FixPosi=set([1])

for _ in range(11):
  for i in nonFixPosi:
    temp=[route[i]]
    for j in FixPosi:
      temp.append(r[i][j]+route[j])
    route[i]=min(temp)
  
  minKey=[]
  minValue=10**4
  for i in nonFixPosi:
    if route[i]==minValue:
      minKey.append(i)
    elif route[i]<minValue:
      minKey=[i]
      minValue=route[i]
  for item in minKey:
    nonFixPosi.remove(item)
    FixPosi.add(item)
  if len(nonFixPosi)<=0:
    break
    
result=[]
for _ in range(h):
  result+=list(map(int,input().split()))
k=collections.Counter(result)
#print(k)
val=0
for i in range(10):
  val+=k[i]*route[i]

print(val)

Submission status: Accepted

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

H, W = map(int, input().split())
c = [[int(i) for i in input().split()] for _ in range(10)]
cnp = np.array(c, dtype=np.int32)

G = csgraph_from_dense(cnp.T)
d = dijkstra(G, indices=1)
# print(d)

l = []
for i in range(H):
    l.extend(map(int, input().split()))


cc = collections.Counter(l)

ans = 0
for k, v in cc.items():
    if k >= 0:
        ans += d[k]*v
print(int(ans))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    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 c in A[i]:
            if c != -1:
                ans += C[c][1]
    print(ans)
    
main()

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 range(w):
        if A[i][j] != -1:
            ans += C[A[i][j]][1]

print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import johnson
h, w = map(int, input().split())
c = johnson([list(map(int, input().split())) for _ in range(10)])

ans = 0
for _ in range(h):
    for j in map(int, input().split()):
        ans += (j != -1) * int(c[j][1])
print(ans)

Submission status: Accepted

Solution code:
h, w = list(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
        ans += c[a[i][j]][1]

print(ans)

Submission status: Accepted

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

h,w=map(int,input().split())
c=np.array([list(map(int,input().split())) for _ in range(10)])
cost=floyd_warshall(c)

ans=0
for _ in range(h):
    inp=map(int,input().split())
    for a in inp:
        if a==-1:
            continue
        ans+=int(cost[a][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(_) for _ in input().split()]

A = [0] * H
for h in range(H):
    A[h] = [int(_) for _ in input().split()]
    
def warshall_floyd(d):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

c = warshall_floyd(c)
ans = 0
for h in range(H):
    for w in range(W):
        if A[h][w] != -1:
            ans += c[A[h][w]][1]
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(x, vis, c):
  global tmp
  if x == 1:
    tmp = min(tmp, c)
    return
  for i in range(10):
    if str(i) in vis:
      continue
    else:
      tami(i, vis+str(i), c+data[x][i])
    
H,W = IL()
data = [IL() for _ in range(10)]
wall = [IL() for _ in range(H)]
cost = [0]*10

for i in range(10):
  if i == 1:
    continue
  else:
    tmp = 100000
    tami(i, str(i), 0)
    cost[i] = tmp
#print(cost)

ans = 0
for h in range(H):
  for w in range(W):
    if abs(wall[h][w]) == 1:
      continue
    else:
      ans += cost[wall[h][w]]
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(0, 10):
    for i in range(0, 10):
        for j in range(0, 10):
            if C[i][j] > C[i][k] + C[k][j]:
                C[i][j] = C[i][k] + C[k][j]
cost = 0
A = [0]*H
for h in range(H):
    for a in map(int, input().split()):
        if a == 1 or a == -1:
            continue
        cost += C[a][1]
print(cost)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
d = [list(map(int,input().split())) for _ in range(10)]
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 _ in range(h):
	for x in map(int,input().split()):
		ans += (x!=-1) * d[x][1]
print(ans)

Submission status: Accepted

Solution code:
import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

def combination(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

sys.setrecursionlimit(10000)

mod = 1000000007

"""
# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]

# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
"""

if __name__ == "__main__":
    N = 10
    H, W = map(int, sys.stdin.readline().split())
    C = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]  # 二次元配列入力　二次元マップみたいな入力のとき
    A = [list(map(int,list(sys.stdin.readline().split()))) for i in range(H)]  # 二次元配列入力　二次元マップみたいな入力のとき

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if C[i][j] > C[i][k] + C[k][j]:
                    C[i][j] = C[i][k] + C[k][j]

    ans = 0
    for h in range(H):
        for w in range(W):
            x = A[h][w]
            if x != -1:
                ans += C[x][1]
    print(ans)

Submission status: Accepted

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

Solution code:
def war(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 = map(int, input().split())

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

    c = war(c,10)

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

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

    print(ans)


main()

Submission status: Accepted

Solution code:
def warshal_floyd(d):
  for k in range(10):
    for i in range(10):
      for j in range(10):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
  return d

h, w = map(int, input().split())
d = [[float('inf') for i in range(10)] for j in range(10)]
for i in range(10):
  l = list(map(int, input().split()))
  for j in range(10):
    d[i][j] = l[j]
d = warshal_floyd(d)
#print(d)

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

#W-F法でiからjへの最小移動コストを求める
res = [c for c in C]
for k in range(10):
    for i in range(10):
        for j in range(10):
            wf = res[i][k] + res[k][j]
            res[i][j] = min(wf,res[i][j])
cost = [r[1] for r in res]

#合計の最小コストを計算
ans = 0
for a in A:
    for x in a:
        if x != -1:
            ans += cost[x]
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)]

res = [0]*10
for i in range(10):
    cnt = C[i]
    while 1:
        prev = [cnt[j] for j in range(10)]
        for k in range(10):
            for l in range(10):
                a = prev[l]+C[l][k]
                if cnt[k] > a:
                    cnt[k] = a
        if prev == cnt or min(cnt[:i]+cnt[i+1:]) == cnt[1]:
            break
    res[i] = cnt[1]
ans = 0
for a in A:
    for x in a:
        if x != -1:
            ans += res[x]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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)
for k, v in dd.items():
  res+= v*scores[k]
print(res)

Submission status: Accepted

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
for k, v in dd.items():
  res+= v*int(dijkstra(c,indices = k)[1])
print(res)

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)

Q = [1]

cost = [float("inf")] * 10
cost[1] = 0


while len(Q) > 0:

    q = Q.pop(0)

    for i in range(10):

        ncos = cost[i]
        nexcos = cost[q] + c[i][q]

        if nexcos < ncos:

            cost[i] = nexcos
            Q.append(i)


ans = 0
cost.append(0)

for i in range(H):

    A = list(map(int,input().split()))

    for a in A:
        ans += cost[a]

print (ans)

Submission status: Accepted

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

for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])
# print(c)
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: Accepted

Solution code:
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
h,w=map(int,input().split())
n=10
d = [list(map(int,input().split())) for i in range(n)] 
wf=warshall_floyd(d)
ans=0
for i in range(h):
    l=map(int,input().split())
    for j in l:
        if j!=-1:ans+=wf[j][1]
print(ans)

Submission status: Accepted

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][1]
print(ans)

Submission status: Accepted

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

    def mp_table(c):
        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])
        return c

    c = mp_table(c)

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

    print(point)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

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

# グラフの辞書化
graph = {}
for i in range(10):
    graph[i] = {}
    for j in range(10):
        graph[i][j] = C[j][i]
        
#print(graph)


from heapq import heappush, heappop

def dijkstra(graph, start, N):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

shrtest = dijkstra(graph, 1, 10)
#print(shrtest)

ans = 0
for sub_a in A:
    for a in sub_a:
        if a == -1 or a == 1:
            continue
        else:
            ans += shrtest[a]
print(ans)

Submission status: Accepted

Solution code:
import heapq
def main():
    H, W = map(int, input().split())
    c = []
    for _ in range(10):
        c.append(list(map(int, input().split())))
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))

    d1 = dict()
    queue = [[0, 1]]
    while queue:
        m, j = heapq.heappop(queue)
        if j not in d1:
            d1[j] = m
            for k in range(10):
                if k not in d1:
                    heapq.heappush(queue, [m+c[k][j], k])

    d = dict()
    for i in range(H):
        for j in range(W):
            if A[i][j] != -1:
                d[A[i][j]] = d.get(A[i][j], 0) + 1

    # print(d1)
    # print(d)
    mag = 0
    for v in d:
        mag += d[v] * d1[v]
    return mag


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
class WarshallFloyd(object):

    def __init__(self, adj):
        """
        ワーシャル・フロイド法によって全頂点間の最短距離を O(|V|^3) で計算する。

        :param adj: 隣接行列 adj[i][j] でi番目の頂点からj番目の頂点へのコストを示す パスがなければINF
        """
        self._dist = adj  # 各頂点間の最短距離 初期値として隣接行列をそのまま用い、[i, i]要素を0に初期化する
        for i in range(len(adj)):
            self._dist[i][i] = 0

        self._solve()

    def _solve(self):
        v_len = len(self._dist)
        for i in range(v_len):  # 経由する頂点
            for j in range(v_len):  # 開始頂点
                for k in range(v_len):  # 終端
                    self._dist[j][k] = min(self._dist[j][k], self._dist[j][i] + self._dist[i][k])

    def distance(self, start, goal):
        return self._dist[start][goal]

    def path(self, start, goal):
        pass


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

wf = WarshallFloyd(C)

ans = 0
for row in A:
    for cell in row:
        if cell == -1:
            continue
        ans += wf.distance(cell, 1)
print(ans)

Submission status: Accepted

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(10):
    if i != 1:
        ans += count[i] * c[i][1]
print(ans)

Submission status: Accepted

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
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    for i in range(2):
        if s[i] == s[i + 1] == s[i + 2]:
            print("Yes")
            return
    print("No")
    return

#B
def B():
    return

#C
def C():
    abcd = list(map(int, S()))
    op = itertools.product(range(2), repeat=3)
    for opx in op:
        ans = abcd[0]
        for num, opi in enumerate(opx):
            if opi:
                ans += abcd[num + 1]
            else:
                ans -= abcd[num + 1]
        if ans == 7:
            print(abcd[0],end="")
            for num, opi in enumerate(opx):
                print(["-", "+"][opi] + str(abcd[num + 1]), end="")
            print("=7")
            return
    return

#D
def D():
    h, w = LI()
    edg = LIR(10)
    for k in range(10):
        for x in range(10):
            for y in range(10):
                edg[x][y] = min(edg[x][k] + edg[k][y], edg[x][y])
    a = LIR(h)
    ans = 0
    for y in range(h):
        for x in range(w):
            if a[y][x] == -1:
                continue
            ans += edg[a[y][x]][1]
    print(ans)
    return

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

Submission status: Accepted

Solution code:
# ABC079D - Wall
import sys
input = sys.stdin.readline

def warshall_floyd():
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if C[i][k] + C[k][j] < C[i][j]:
	                C[i][j] = C[i][k] + C[k][j]
    return C


def main():
    global C
    H, W = tuple(map(int, input().split()))
    C = list(list(map(int, input().split())) for _ in range(10))
    A = tuple(tuple(map(int, input().split())) for _ in range(H))
    warshall_floyd()
    ans = sum(sum(C[i][1] for i in a if i != -1) for a in A)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC079D - Wall
import sys
input = sys.stdin.readline

def warshall_floyd():
    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])
    return C


def main():
    global C
    H, W = tuple(map(int, input().split()))
    C = list(list(map(int, input().split())) for _ in range(10))
    A = tuple(tuple(map(int, input().split())) for _ in range(H))
    warshall_floyd()
    ans = sum(sum(C[i][1] for i in a if i != -1) for a in A)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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(10):
    if i != 1:
        ans += count[i] * c[i][1]
print(ans)

Submission status: Accepted

Solution code:
def WarshallFloyd(M):
    N = len(M)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M

H, W = [int(i) for i in input().split()]
C = [[int(i) for i in input().split()] for _ in range(10)]
A = [[int(i) for i in input().split()] for _ in range(H)]

M = WarshallFloyd(C)

ans = 0
for r in A:
    for a in r:
        if a >= 0:
            ans += M[a][1]
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall as fw

def main():
    h, w = map(int, input().split())
    link = [list(map(int, input().split())) for i in range(10)]

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

    link = fw(link)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    def dijkstra_search(s):
        from heapq import heappush, heappop
        d = [INF] * n
        searched = [False] * n
        d[s] = 0
        searched[s] = True
        edge_list = []
        count = 1
        for i in edge[s]:
            heappush(edge_list,i)
        while edge_list:
            min_d,min_v = heappop(edge_list)
            if searched[min_v] or min_d > d[min_v]:
                continue
            v = min_v
            d[v] = min_d
            searched[v] = True
            count += 1
            for i,j in edge[v]:
                next_d = i+d[v]
                if not searched[j]:
                    heappush(edge_list,(next_d,j))
            if count == n:
                break
        return d
    
    h,w = map(int,input().split())
    n = 10
    route = []
    route = [list(map(int,input().split())) for _ in range(n)]
    INF = float('inf')
    edge = [[] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            edge[j].append((route[i][j],i))
    dist = dijkstra_search(1)
    hw = [list(map(int,input().split())) for _ in range(h)]
    ans = 0
    for i in hw:
        for j in i:
            if not j == -1:
                ans += dist[j]
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################

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

n=10
w=81

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(10):
    clist = list(map(int, input().split()))
    clist[i]=99999
    #print(clist)
    for j in range(len(clist)):
        if clist[j]!=99999:
            cost[j][i]=clist[j]

costs=dijkstra(1,n,w,cost)
kotae=0
for i in range(h):
    alist = list(map(int, input().split()))
    for al in alist:
        if al!=-1:
            kotae+=costs[al]

print(kotae)

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import floyd_warshall as wf
input = sys.stdin.readline

def main():
  H, W = map(int, input().split())
  link = [list(map(int, input().split())) for i in range(10)]
  a = [list(map(int, input().split())) for i in range(H)]
  
  link = wf(link)
  
  ans = 0
  for i in range(H):
    for j in range(W):
      if a[i][j] != -1:
        ans += link[a[i][j]][1]
  print(int(ans))

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
c=[list(map(int,input().split())) for _ in [0]*10]
a=[list(map(int,input().split())) for _ in [0]*h]
cost=[float('inf')]*10
cost[1]=0
for _ in [0]*9:
    for i in range(10):
        cost[i]=min(c[i][j]+cost[j] for j in range(10))
ans=0
for i in range(h):
    for j in range(w):
        if a[i][j]>=0:
            ans+=cost[a[i][j]]
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
D = []
for i in range(10):
  Cs = list(map(int, input().split()))
  D.append(Cs)
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])
#print(D)
r = 0
for i in range(H):
  As = list(map(int, input().split()))
  for j in range(W):
    A = As[j]
    if A < 0:
      continue
    r += D[A][1]
print(r)