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

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)

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
tra=[list(map(int,input().split())) for i in range(10)]
ll=[[tra[i][j] for j in range(10)] for i in range(10)]
for i in range(10**3-1):
    for i in range(10):
        for j in range(10):
            if i!=j:
                ll[i][j]=min(ll[i][j],min(ll[i][o]+tra[o][j] for o in range(10) if o!=i and o!=j))
ans=0
for i in range(h):
    for j in map(int,input().split()):
        if j==-1 or j==1:continue
        ans+=ll[j][1]
print(ans)

Submission status: Accepted

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

def submit():
    h, w = map(int, input().split())
    costs = [list(map(int, input().split())) for _ in range(10)]
    a = [list(map(int, input().split())) for _ in range(h)]

    # i, j間の最短距離を求める
    dist = {(i, j): float('inf') for i in range(10) for j in range(10)}
    for i in range(10):
        for j in range(10):
            dist[(i, j)] = costs[i][j]

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

    ans = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] < 0:
                continue    
            ans += dist[(a[i][j], 1)]
    print(ans)


submit()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w = inpl()
d = [inpl() for _ in range(10)]
a = [inpl() for _ in range(h)]
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])
res = 0
for i in range(h):
    for j in range(w):
        now = a[i][j]
        if now == -1:
            continue
        res += d[now][1]
        # print(res,now)
print(res)

Submission status: Accepted

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

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

from scipy.sparse.csgraph import floyd_warshall

C = floyd_warshall(C)

ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] < 0: continue
        ans += int(C[A[i][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)]
wall = [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 wall[i][j] != -1:
            ans += C[wall[i][j]][1]
print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd(c, d):
    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])
                if k == 1:
                    d[j] = c[j][k]
    return d

h, w = map(int, input().split())
c = [[int(i) for i in input().split()] for j in range(10)]
a = [[int(i) for i in input().split()] for j in range(h)]
dist = [0] * 10
ans = 0
warshall_floyd(c, dist)

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

print(ans)

Submission status: Accepted

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

c=[list(map(int,input().split())) for i in range(10)]
a=[list(map(int,input().split())) for i in range(h)]
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]>=0:
            ans+=c[a[i][j]][1]
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    H, W = (int(i) for i in input().split())
    c = [[int(i) for i in input().split()] for j in range(10)]
    A = [[int(i) for i in input().split()] for j in range(H)]
    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra
    csr = csr_matrix(c, dtype=np.int32)
    ret = dijkstra(csr)
    ans = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == -1:
                continue
            cur = A[h][w]
            ans += int(ret[cur][1])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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
inf=1<<32
d = [[inf for i in range(10)] for _ in range(10)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(10):
    for j in range(10):
        d[i][j]=c[i][j]
for i in range(10):
    d[i][i] = 0 #自身のところに行くコストは０
x=warshall_floyd(d)
ans=0
for i in range(h):
    for j in range(w):
        if a[i][j]==-1:
            continue
        ans+=x[a[i][j]][1]
print(ans)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    H,W=map(int, input().split())
    c=[list(map(int, input().split())) for _ in range(10)]
    A=[tuple(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] >= 0:
                ans += c[A[i][j]][1]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def floyd_warshall(dist):
    v = len(dist)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

H, W = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
floyd_warshall(c)
A = [list(map(int, input().split())) for _ in range(H)]
ans = 0
for row in A:
    for a in row:
        if a != -1:
            ans += c[a][1]
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    h,w = LI()
    c = LIR(10)
    for k in range(10):
        for i in range(10):
            for j in range(10):
                nc = c[i][k]+c[k][j]
                if nc < c[i][j]:
                    c[i][j] = nc
    a = LIR(h)
    ans = 0
    for i in a:
        for j in i:
            if j < 0:
                continue
            ans += c[j][1]
    print(ans)
    return

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

Submission status: Accepted

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):
            d = C[i][k] + C[k][j]
            if C[i][j] > d:
                C[i][j] = d

cost = [C[j][1] for j in range(10)]
ans = 0

for _ in range(H):
    for n in map(int, input().split()):
        if n == -1:
            continue
        ans += cost[n]
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
dist=[list(map(int,input().split())) for _ in range(10)]
#print(dist)
for k in range(10):
    for i in range(10):
        for j in range(10):
            if dist[i][j]>dist[i][k]+dist[k][j]:
                dist[i][j]=dist[i][k]+dist[k][j]
ans=0
#print(dist)
#print(dist[1][8],end=' dist 1 to 8 \n')
a=[list(map(int,input().split())) for _ in range(h)]
for j in a:
    for i in j:
        if i!=-1:
            ans+=dist[i][1]
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc079/tasks/abc079_d
# 16:03-17:18


def dijkstra(d, s, t):
    INF = 10**10
    dist = [INF] * 10
    dist[s] = 0
    checked = []

    while True:
        # 未チェックの中から，sからのコストが現状最も小さいものを見つける
        nodes = [node for node in range(10) if node not in checked]
        shortest_node, cost = nodes[0], dist[nodes[0]]

        for node in nodes:
            if dist[node] < cost:
                shortest_node, cost = node, dist[node]
        
        if shortest_node == t:
            return dist[t]

        checked.append(shortest_node)
        
        nodes = [node for node in range(10) if node not in checked]
        for node in nodes:
            dist[node] = min(
                dist[shortest_node] + d[shortest_node][node], dist[node])


def main():
    H, W = map(int, input().split())

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

    A = [None] * H
    for i in range(H):
        A[i] = list(map(int, input().split()))

    shortests = [None] * 10
    for s in range(10):
        if s == 1:
            shortests[s] = 0
        else:
            shortests[s] = dijkstra(c, s, 1)
    
    counts = [0] * 10
    for h in range(H):
        for w in range(W):
            if A[h][w] == -1:
                continue

            counts[A[h][w]] += 1
    
    ans = 0
    for i in range(10):
        ans += counts[i] * shortests[i]
    
    return ans


print(main())

Submission status: Accepted

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)]
# 有向グラフと考えらる
C = floyd_warshall(C)
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] != -1:
            ans += C[A[i][j]][1]  # 頂点1に到達するためのコスト
print(int(ans))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import Counter
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):
    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])

    ctr = Counter(Aij for Ai in A for Aij in Ai)
    print(sum(ctr[n] * c[n][1] for n in range(10)))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    c = [[int(next(tokens)) for _ in range(9 - 0 + 1)] for _ in range(9 - 0 + 1)]  # type: "List[List[int]]"
    A = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  # type: "List[List[int]]"
    solve(H, W, c, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    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)]

    warshall_floyd(c)
    res = 0
    for i in range(h):
        for j in range(w):
            x = a[i][j]
            if x != -1:
                res += c[x][1]
    print(res)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

for k in range(10):
  for i in range(10):
    for j in range(10):
      c[i][j] = min(c[i][j], c[i][k]+c[k][j])
      
ans = 0
for i in range(h):
  for j in range(w):
    if A[i][j]!=-1:
      ans += c[A[i][j]][1]
      #print(A[i][j])

print(ans)

Submission status: Accepted

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

for _ in range(10):
  for i in range(10):
    for j in range(10):
      if i==j:
        continue
      for k in range(10):
        if i==k or k==j:
          continue
        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: Accepted

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

for k in range(10):
  for i in range(10):
    for j in range(10):
      if S[i][j] > S[i][k] + S[k][j]:
        S[i][j] = S[i][k] + S[k][j]
        
D = {}
for i in range(H):
  line = list(map(int, input().split()))
  for j in line:
    if j in D:
      D[j] += 1
    else:
      D[j] = 1
magic = 0
for k in D:
  if k != -1:
    magic += S[k][1] * D[k]
print(magic)

Submission status: Accepted

Solution code:
from collections import Counter
def solve():
    H, W = map(int, input().split())
    C = [list(map(int, input().split())) for i in range(10)]
    A = []
    for i in range(H):
        a = list(map(int, input().split()))
        A += a


    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])
    
    counter = Counter(A)

    ans = 0
    for num, count in counter.items():
        if num == -1:
            continue
        ans += C[num][1] * count
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# coding: utf-8
from heapq import heappop, heappush

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

INF=10**11

G=[]

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

d=[INF for i in range(10)]
d[1]=0

used=[False for i in range(10)]


heap=[]
heappush(heap,(d[1],1))

#それぞれのノードから1に行く最短距離を求めるダイクストラ
while heap:
    d_u, u = heappop(heap)
    used[u] = True
    if d[u] < d_u:
        continue
    for v in range(10):
        if v==u:
            continue
        if not(used[v]) and d_u + G[v][u] < d[v]:
            d[v] = d_u + G[v][u]
            heappush(heap,(d[v],v))

ans=0

for i in range(H):
    line=list(map(int,input().split()))
    for j in range(W):
        if line[j]!=-1:
            ans+=d[line[j]]

print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc079/tasks/abc079_d
import sys
input = sys.stdin.readline
# int(input()) # 入力が1つ
h, w = map(int, input().split()) # 入力が複数

graph = []
for _ in range(10):
    row = [int(i) for i in input().split()]
    graph.append(row)

def warshall_floyd(graph, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
warshall_floyd(graph, 10)
ans = 0
for _ in range(h):
    row = [int(i) for i in input().split()]
    for wall in row:
        if wall == -1 or wall == 1:
            continue
        ans += graph[wall][1]
print(ans)

Submission status: Accepted

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


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

cnt = 0
for i in range(H):
    for j in range(W):
        here = A[i][j]
        if here not in [-1, 1]:
            cnt += C[here][1]

print(cnt)

Submission status: Accepted

Solution code:
import heapq
import math
class Graph:
    def __init__(self,v,w_e,w_v = None):
        super().__init__()
        self.v = v

        self.w_v = w_v
        self.w_e = [{} for _ in [0]*self.v]


        self.neighbor = [[] for _ in [0]*self.v]
        for a_i,b_i,w_i in w_e:
            self.w_e[a_i][b_i] = w_i#weight of edge
            self.neighbor[a_i].append(b_i)

    def dijkstra(self,v_n):
        d = [10**18]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

def main():
    h,w = tuple([int(t)for t in input().split()])

    c = [[int(t) for t in input().split()]for _ in [0]*10]

    a = [[int(t) for t in input().split()]for _ in [0]*h]

    counter = [0]*10
    for a_i in a:
        for a_ij in a_i:
            if a_ij != -1:
                counter[a_ij]+=1

    w_e = []
    for i in range(10):
        for j in range(10):
            w_e.append((i,j,c[i][j]))
    
    g = Graph(10,w_e)

    routes = []
    for i in range(10):
        routes.append(g.dijkstra(i)[0])

    ans = 0
    for i in range(10):
        if i!=1:
            ans += routes[i][1]*counter[i]

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    H,W = map(int,input().split())
    graph = []
    for i in range(10):
        graph.append(list(map(int,input().split())))
    c = []
    for j in range(H):
        c.append(list(map(int,input().split())))

    dist = np.array(dijkstra(graph),dtype="int32")
    ans = 0
    for i in range(H):
        for j in c[i]:
            if j != -1:
                ans += dist[j][1] 
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

# T[j][i]: cost from j to i, O(V^3)
# T[j][i] = 0 if j == i


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


warshall_floyd(C, 10)

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

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:
h,w = map(int,input().split())
c = [[int(i) for i in input().split()] for _ in range(10)]
A = {i:0 for i in range(10)}
for _ in range(h):
  for i in input().split():
    if i != '-1':
      A[int(i)] += 1
    

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

ans = 0
for i in range(10):
  ans += c[i][1] * A[i]
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra as di
from collections import Counter
h,w = map(int, input().split())

magic = [list(map(int, input().split())) for i in range(10)]
grid = Counter()
for i in range(h):
    grid.update(Counter(map(int, input().split())))


# 要素はfloat なので注意
dmagic = di(magic)

ans = 0
for i in range(10):
    if i == 1 or i not in grid:
        continue
    ans += dmagic[i][1] * grid[i]

print(int(ans))

Submission status: Accepted

Solution code:
def main():
    H,W = map(int,input().split())
    cost = [[2**60]*10 for _ in range(10)]
    for i in range(10):
        cost[i][i] = 0
    for j in range(10):
        for i,c in enumerate(tuple(map(int,input().split()))):
            cost[j][i] = c
    a = [tuple(map(int,input().split()))for _ in range(H)]
    for k in range(10):
        for i in range(10):
            for j in range(10):
                cost[i][j] = min(cost[i][j],cost[i][k]+cost[k][j])
    ans = 0
    for h in range(H):
        for w in range(W):
            if a[h][w] == -1:continue
            ans += cost[a[h][w]][1]
    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())))
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):
            C[i][j]=min(C[i][j],C[i][k]+C[k][j])
cnt=0
for i in range(h):
    for j in range(w):
        if A[i][j]==-1 or A[i][j]==1:
            continue
        cnt+=C[A[i][j]][1]
print(cnt)

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

Submission status: Accepted

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)]
n = 10
c = floyd_warshall(c)
ans = 0
for i in a:
    for j in i:
        if j!=-1: ans += c[j][1]
print(int(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)]
n = 10
for k in range(n):
    for i in range(n):
        for j in range(n):
            c[i][j] = min(c[i][j],c[i][k]+c[k][j])
ans = 0
for i in a:
    for j in i:
        if j!=-1: ans += c[j][1]
print(ans)

Submission status: Accepted

Solution code:
import itertools
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)]
a = list(itertools.chain.from_iterable(a))
b = collections.Counter(a)
ans = 0

def bfs(x):
    if x[-1]==1:
        global s
        buf = 0
        for i in range(len(x)-1):
            buf += c[x[i]][x[i+1]]
        s = min(s,buf)
    else:
        for i in range(10):
            if not i in x:
                bfs(x+[i])

for i in b:
    if not i in [1,-1]:
        s = 10**9
        bfs([i])
        ans += s*b[i]
print(ans)

Submission status: Accepted

Solution code:
import heapq
def dijkstra_heap(s,C):
  #始点sから各頂点への最短距離
  d = [float("inf")] * 10
  used = [False] * 10
  d[s] = 0
  used[s] = True
  edgelist = []
  #edgelist : (sからの暫定(未確定)最短距離,頂点)のリスト
  #edge[s] : sから出る枝の(重み,終点)の配列
  for i,w in enumerate(C[s]):
    heapq.heappush(edgelist,[w,i]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    minedge = heapq.heappop(edgelist)
    #minedge : (sからの(確定)最短距離,頂点)
    v = minedge[1]
    if used[v]:
      continue
    d[v] = minedge[0]
    used[v] = True
    for i,w in enumerate(C[v]):
      if not used[i]:
        heapq.heappush(edgelist,[d[v]+w,i])
  return d

H, W = map(int, input().split())
C = [[] for _ in range(10)]
for i in range(10):
  c = list(map(int, input().split()))
  for j in range(10):
    C[j].append(c[j])
d = dijkstra_heap(1,C)
#print(d)
ans = 0
for i in range(H):
  A = list(map(int, input().split()))
  for a in A:
    if a>=0:
      ans += d[a]
print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n): #iから直接jのときと頂点kを経由した場合の比較
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

##############################
h,w=map(int,input().split())
field=[list(map(int,input().split())) for i in range(10)]
wall=[[int(i) for i in input().split()] for i in range(h)]
n=10

ans=0
d=warshall_floyd(field)
for i in wall:
    for j in i:
        if j==-1:
            pass
        else:
            ans+=d[j][1]
print(ans)

Submission status: Accepted

Solution code:
def warshallFloyd(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

N = 10
H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(N)]
A = [list(map(int, input().split())) for _ in range(H)]
D = warshallFloyd(C)
ans = 0
ans = sum(D[A[i][j]][1] if A[i][j] != -1 else 0 for i in range(H) for j in range(W))
print(ans)