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:
class Digraph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=set(vertex)

        self.edge_number=0
        self.vertex_number=len(vertex)

        self.adjacent_out={v:{} for v in vertex} #出近傍(vが始点)
        self.adjacent_in={v:{} for v in vertex} #入近傍(vが終点)

    #頂点の追加
    def add_vertex(self,*adder):
        for v in adder:
            if v not in self.vertex:
                self.adjacent_in[v]={}
                self.adjacent_out[v]={}

                self.vertex_number+=1
                self.vertex.add(v)

    #辺の追加(更新)
    def add_edge(self,From,To,weight=1):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To not in self.adjacent_in[From]:
            self.edge_number+=1

        self.adjacent_out[From][To]=weight
        self.adjacent_in[To][From]=weight

    #辺を除く
    def remove_edge(self,From,To):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(w)

        if To in self.adjacent_out[From]:
            del self.adjacent_out[From][To]
            del self.adjacent_in[To][From]
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*vertexes):
        for  v in vertexes:
            if v in self.vertex:
                self.vertex_number-=1

                for u in self.adjacent_out[v]:
                    del self.adjacent_in[u][v]
                    self.edge_number-=1
                del self.adjacent_out[v]

                for u in self.adjacent_in[v]:
                    del self.adjacent_out[u][v]
                    self.edge_number-=1
                del self.adjacent_in[v]

    #Walkの追加
    def add_walk(self,*walk):
        pass

    #Cycleの追加
    def add_cycle(self,*cycle):
        pass

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.vertex

    #グラフに辺が存在するか否か
    def edge_exist(self,From,To):
        if not(self.vertex_exist(From) and self.vertex_exist(To)):
            return False
        return To in self.adjacent_out[From]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #出次数
    def out_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_out[v])

    #入次数
    def in_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_in[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return self.out_degree(v)-self.in_degree(v)

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        pass

def Dijkstra_All(D,From,with_path=False):
    """Dijksta法を用いて,単一始点Fromからの距離を求める.

    D:辺の重みが全て非負の有向グラフ
    From:始点
    To:終点
    with_path:最短路も含めて出力するか?

    (出力の結果)
    with_path=True->(距離,最短経路の辿る際の前の頂点)
    with_path=False->距離
    """
    from copy import copy

    T={v:float("inf") for v in D.vertex}
    T[From]=0

    if with_path:
        Prev={v:None for v in D.vertex}

    Q=copy(D.vertex)

    Flag=False
    while Q:
        u=min(Q,key=lambda u:T[u])
        Q.remove(u)

        for v in D.adjacent_out[u]:
            if T[v]>T[u]+D.adjacent_out[u][v]:
                T[v]=T[u]+D.adjacent_out[u][v]

                if with_path:
                    Prev[v]=u

    if with_path:
        return (T,Prev)
    else:
        return  T

#逆グラフの作成
def Inverse_Graph(D):
    """有向グラフDの全ての辺の向きを変えたグラフを出力する.

    D:有向グラフ
    """
    from copy import deepcopy

    F=Digraph(D.vertex)

    F.edge_number=D.edge_number
    F.vertex_number=D.vertex_number

    F.adjacent_in=deepcopy(D.adjacent_out)
    F.adjacent_out=deepcopy(D.adjacent_in)

    return F

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

D=Digraph(range(10))
for i in range(10):
    C=list(map(int,input().split()))
    for j in range(10):
        D.add_edge(i,j,C[j])

D=Inverse_Graph(D)
T=Dijkstra_All(D,1)

Count={x:0 for x in range(-1,10)}

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

X=0
for a in range(10):
    X+=Count[a]*T[a]

print(X)

Submission status: Accepted

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


for k in range(10):
    for i in range(10):
        for j in range(10):
            if c[i][j] > c[i][k] + c[k][j]:
                c[i][j] = c[i][k] + c[k][j]
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] >= 0:
            ans += c[a[i][j]][1]

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
C = []
for i in range(10):
  c = list(map(int, input().split()))
  C.append(c)
A = []
for i in range(H):
  a = list(map(int, input().split()))
  A.append(a)
  
for k in range(10):
  for i in range(10):
    for j in range(10):
      if C[i][k]+C[k][j] < C[i][j]:
        C[i][j] = C[i][k] + C[k][j]
        
ans = 0
for i in range(H):
  l = A[i]
  for j in range(W):
    n = l[j]
    if (n==0) or (n>1):
      ans += C[n][1]
print(ans)

Submission status: Accepted

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

r = range(10)
c = [[int(i) for i in input().split()] for _ in r]

for k in r:
    for i in r:
        for j in r:
            c[i][j] = min(c[i][j], c[i][k] + c[k][j])
else:
    a = [[int(i) for i in input().split()] for _ in range(h)]
    print(sum(c[i][1] for i in sum(a, []) if i != -1))

Submission status: Accepted

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

r = range(10)
c = [[int(i) for i in input().split()] for _ in r]
a = [[int(i) for i in input().split()] for _ in range(h)]

for k in r:
    for i in r:
        for j in r:
            c[i][j] = min(c[i][j], c[i][k] + c[k][j])
else:
    print(sum(c[i][1] for i in sum(a, []) if i != -1))

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
h, w = map(int, input().split())
c = [[*map(int, input().split())] for _ in range(10)]
a = [[*map(int, input().split())] for _ in range(h)]
d = [c[i][1] for i in range(10)]
for i in range(10):
    for j in range(10):
        d[j] = min(d[j], min(c[j][k] + d[k] for k in range(10)))
d += [0]
print(sum(d[i] for i in sum(a,[])))

Submission status: Accepted

Solution code:
# G[i][j]: 頂点v_iから頂点v_jへ到達するための辺コストの和
# クラスにしてしまったけど、これ遅いのでクラスじゃ無い方が良い
class Warshall_Floyd:
    def __init__(self, V):
        self.V = V
        self.G = [[float('inf')] * self.V for i in range(self.V)]

    def add_edge(self, fr, to, cost):
        self.G[fr][to] = cost

    def add_multi_edge(self, v1, v2, cost):
        self.G[v1][v2] = cost
        self.G[v2][v1] = cost

    def solve(self):
        for i in range(self.V):
            self.G[i][i] = 0
        for k in range(self.V):
            for i in range(self.V):
                for j in range(self.V):
                    if self.G[i][k] != float("inf") and self.G[k][j] != float('inf'):
                        self.G[i][j] = min(self.G[i][j], self.G[i][k] + self.G[k][j])

    def if_negative(self):
        for i in range(self.V):
            if self.G[i][i] < 0:
                return True
        return False

    def dist(self, fr, to):
        return self.G[fr][to]


G = Warshall_Floyd(10)

H, W = map(int, input().split())
for i in range(10):
    for j, c in enumerate(input().split()):
        G.add_edge(i, j, int(c))
G.solve()


ans = 0
for i in range(H):
    for j, a in enumerate(input().split()):
        if a != "-1":
            ans += G.dist(int(a), 1)

print(ans)

Submission status: Accepted

Solution code:
# 62


h, w = map(int, input().split())
dp = [[int(x) for x in input().split()] for y in range(10)]
a_l = [[int(x) for x in input().split()] for y in range(h)]

for k in range(10):
    for j in range(10):
        for i in range(10):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
            
ans = 0
for i in range(h):
    for _a in a_l[i]:
        if _a == -1:
            continue
        ans += dp[_a][1]

print(ans)

Submission status: Accepted

Solution code:
INF = 10 ** 20
H, W = map(int, input().split())
power = 0
graph = []
for i in range(10):
  graph.append(list(map(int, input().split())))

for k in range(10):
  for i in range(10):
    for j in range(10):
      graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
  
for h in range(H):
  A = list(map(int, input().split()))
  for w in range(W):
    if A[w] == -1:
      continue
    else:
      power += graph[A[w]][1]

print(power)

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

d = warshall_floyd(c)
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:
#!/usr/bin/env python3
import sys

def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):
    import numpy as np
    from scipy.sparse.csgraph import floyd_warshall
    from itertools import chain
    mat = floyd_warshall(np.array(c, dtype=np.int64), directed=True)    
    return int(sum(mat[a][1] for a in filter(lambda x: x >= 0, chain.from_iterable(A))))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    c = [[int(next(tokens)) for _ in range(9 - 0 + 1)] for _ in range(9 - 0 + 1)]  # type: "List[List[int]]"
    A = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  # type: "List[List[int]]"
    print(solve(H, W, c, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: 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)]
dp = [float("INF")]*(10)
dp[1] = 0
cnt = 1
while cnt < 10:
    cnt += 1
    for i in range(10):
        for j in range(10):
            dp[i] = min(dp[i],dp[j]+C[i][j])
ans = 0
for i in range(H):
    for j in range(W):
        a = A[i][j]
        if a != -1:
            ans += dp[a]
print(ans)

Submission status: Accepted

Solution code:
import collections
import itertools

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

a_1D =list(itertools.chain.from_iterable(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])

a_cnt = collections.Counter(a_1D)

total = 0
for i,j in a_cnt.items():
    if i == -1:
        pass
    else:
        total += c[i][1]*j

print(total)

Submission status: Accepted

Solution code:
from collections import defaultdict
dicA = defaultdict(int) 

H,W = map(int,input().split())
C = []
min_step = []
for i in range(10):
  temp = list(map(int,input().split()))
  C.append(temp)
  min_step.append(temp[1])
#print(C)
#print(min_step)

def dfs(n,k,now): #0indexの数字nから1に行くのに最短の値。nowステップ進んで今kにいる。
  if now > min_step[n]:
    return
  for i in range(10):
    if i == 1: #kから0に行ったときは、現状の最短とどちらが近いかを比較。
      #print(min_step[n],now+ C[k][1])
      min_step[n] = min(min_step[n],now+ C[k][1])
    if i != k:
      if C[k][i]+now < min_step[n]: #iを経由しても現状の最短よりも近い。
        #print(n,i,now,C[k][i])
        dfs(n,i,C[k][i]+now)

for i in range(10):
  if i == 1:
    continue
  for j in range(10):
    if i!=j:
      dfs(i,j,C[i][j])

#print(min_step)

for i in range(H):
  temp = list(map(int,input().split()))
  for j in range(W):
    if temp[j] == -1:
      continue
    dicA[temp[j]] +=1 #数字を0indexに
ans = 0
#print(dicA)
for x in dicA.keys():
  ans += min_step[x]*dicA[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)]

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

dist=warshall_floyd(c)

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

Submission status: Accepted

Solution code:
from itertools import permutations
from heapq import heappush,heappop

INF=10**12

def dijkstra(G, start = 0, INF=INF):
    
    d = [INF for i in range(len(G))]
    d[start] = 0
    
    que = []
    heappush(que, (0, start))

    while len(que) != 0:
        p = heappop(que)
        v = p[1]
        
        if d[v] < p[0]:
            continue
            
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                heappush(que, (d[u], u))
    
    return d

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

G=[{} for _ in range(10)]
for i in range(10):
  for j in range(10):
    G[i][j] = c[i][j]

dist=[0]*10
for i in range(10):
  d = dijkstra(G,i)
  dist[i] = d[1]

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

arr=[list(map(int,input().split())) for i in range(10)]
wall=[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):
            arr[j][k]=min(arr[j][i]+arr[i][k],arr[j][k])

ans = 0
for i in range(H):
    for item in wall[i]:
        if item<0:
            continue
        ans += arr[item][1]  
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
INF=float('inf')

a=[]
for _ in range(10):
  c=list(map(int,input().split()))
  a.append(c)
  
for i in range(10):
  for j in range(10):
    for k in range(10):
      a[j][k]=min(a[j][k],a[j][i]+a[i][k])


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

Submission status: Accepted

Solution code:
import copy
L=[[j for j in range(10)] for i in range(10)]
H,W=map(int,input().split())
costs=list()
costs2=list()
for i in range(10):
  L1=list(map(int,input().split()))
  costs.append(L1[1])
  costs2.append(L1[1])
  L[i]=L1
for i in range(12):#繰り返し
  for j in range(10):#costsのそれぞれに対し
    for k in range(10):#costs[j]=min(costs[j],costs[k]+jからkのコスト
      costs2[j]=min(costs2[j],costs[k]+L[j][k])
  costs=copy.copy(costs2)
costs.append(0)
s=0
for i in range(H):
  A=list(map(int,input().split()))
  s+=sum([costs[i] for i in A])
print(s)

Submission status: Accepted

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


def read():
    H, W = map(int, input().strip().split())
    N = 10
    C = []
    for i in range(N):
        c = list(map(int, input().strip().split()))
        C.append(c)
    A = []
    for i in range(H):
        a = list(map(int, input().strip().split()))
        A.append(a)
    return H, W, N, C, A


def warshall_floyd(N, G, INF=10**7):
    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


def solve(H, W, N, C, A):
    D = warshall_floyd(N, C)
    ans = 0
    for i in range(H):
        for j in range(W):
            a = A[i][j]
            if a >= 0:
                ans += D[a][1]
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:



h,w = map(int, raw_input().split())
cost = []
for _ in range(10): 
	cost.append(map(int,raw_input().split()))


mat = [map(int, raw_input().split()) for ii in range(h)]

h = {(u,v):cost[u][v] for u in range(10) for v in range(10)}
for t in range(10):
	for u in range(10):
		for v in range(10):
			for w in range(10):
				h[(u,v)] = min(h[(u,v)], h[(u,w)] + h[(w,v)])
cumul = 0
for e in mat:
	for el in e:
		if el != -1:
			cumul += h[(el,1)]
print cumul

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())))
cost = [float("inf") for i in range(10)]
flag = [False for i in range(10)]
cost[1] = 0
test = [1]
while test:
    num = test.pop(0)
    flag[num] = True
    for i in range(10):
        cost[i] = min(cost[i], cost[num] + c[i][num])
    temp = [[cost[i], i] for i in range(10)]
    temp.sort()
    for i in range(10):
        if flag[temp[i][1]] == True:
            continue
        else:
            test.append(temp[i][1])
            break
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == -1:
            continue
        else:
            ans += cost[a[i][j]]
print(ans)

Submission status: Accepted

Solution code:
#ワシャフ
INF = 10**9

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

#iからjにするのに必要な魔力量
c = [list(map(int,input().split())) for i in range(10)]

dp = [[(INF if i!=j else 0) for j in range(10)]for i in range(10)]
for k in range(0,10,1):
    for i in range(0,10,1):
        for j in range(0,10,1):
            c[i][j] = min(c[i][j],c[i][k]+c[k][j])


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

Submission status: Accepted

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

H,W = map(int,readline().split())
C = [None] * 10
for i in range(10):
  C[i] = list(map(int,readline().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])

from collections import defaultdict
wall = defaultdict(int)
for i in range(H):
  for w in list(map(int,readline().split())):
    wall[w] += 1
  
ans = 0
for key,value in wall.items():
  if key == -1:
    continue
  ans += value * C[key][1]
  
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

h,w=map(int,input().split())
c=[]
dic=defaultdict(int)
for _ in range(10): c.append(list(map(int,input().split())))
for _ in range(h):
    temp=list(map(int,input().split()))
    for i in temp: dic[i]+=1
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 item in dic.items():
    if item[0]>=0: ans+=item[1]*c[item[0]][1]
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def warshall_floyd(dist):
    v_count = len(dist[0])

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

    return dist


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

    results = warshall_floyd(c)

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
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)]
    h = [(0,1)]
    V = [-1]*10
    while h:
        # print(h)
        m, n = heappop(h)
        if V[n] > -1:
            continue
        V[n] = m
        for i in range(10):
            if V[i] == -1:
                heappush(h, (m+C[i][n],i))
    # print(V)
    ans = 0
    for a in A:
        for b in a:
            if b > -1:
                ans += V[b]
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import copy
import heapq
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])

    def search(self, s, g):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]



def solve():
    h, w = getList()
    cost = []
    for i in range(10):
        cost.append(getList())

    V = 10
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if cost[i][k] != INF and cost[k][j] != INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

    wall = []
    ans = 0
    for i in range(h):
        for num in getList():
            if num != -1:
                ans += cost[num][1]
    print(ans)
    # print(cost)
    return
def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense

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


G = csgraph_from_dense(C, null_value=0)

d = floyd_warshall(G)

ans = 0

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


print(int(ans))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w = MAP()
c = []
for i in range(10):
    c.append(LIST())
a = []
for i in range(h):
    a.append(LIST())

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

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 math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w = MAP()
c = []
for i in range(10):
    c.append(LIST())
a = []
for i in range(h):
    a.append(LIST())

chk = True
while chk:
    chk = False
    for i in range(10):
        for j in range(10):
            for k in range(10):
                if c[i][j] > c[i][k]+c[k][j]:
                    c[i][j] = c[i][k]+c[k][j]
                    chk = True

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

dist=[]
dist.extend(c)
for i in range(10):
  for j in range(10):
    for k in range(10):
      if dist[j][k]>dist[j][i]+dist[i][k]:
        dist[j][k]=dist[j][i]+dist[i][k]
print(sum(dist[a[i][j]][1] for i in range(h) for j in range(w) if a[i][j]>-1))