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 sys
#import numpy as np
import itertools
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford, floyd_warshall
#sys.setrecursionlimit(10000)

H, W = [int(i) for i in input().split()]

rows = []
cols = []
weights = []

"""
for _ in range(M):
    # u v 間のコスト
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(a)
"""
for i in range(10):
    # u v 間のコスト
    c = [int(j) for j in input().split()]
    #print(c)
    for j in range(10):
        rows.append(i)
        cols.append(j)
        weights.append(c[j])

#graph = coo_matrix((weights, (rows, cols)), shape=(10, 10)).tocsr()
graph = coo_matrix((weights, (cols, rows)), shape=(10, 10)).tocsr()

#d1 = dijkstra(graph, indices=1, directed=True, unweighted=False)
d2 = floyd_warshall(graph, directed=True, unweighted=False)
#print(d2)

ans = 0

for i in range(H):
    a = [int(_) for _ in input().split()]
    for j in a:
        if j != -1:
            ans += d2[1][j]

print(int(ans))

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import itertools
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford
#sys.setrecursionlimit(10000)

H, W = [int(i) for i in input().split()]

rows = []
cols = []
weights = []

"""
for _ in range(M):
    # u v 間のコスト
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(a)
"""
for i in range(10):
    # u v 間のコスト
    c = [int(j) for j in input().split()]
    #print(c)
    for j in range(10):
        rows.append(i)
        cols.append(j)
        weights.append(c[j])

#graph = coo_matrix((weights, (rows, cols)), shape=(10, 10)).tocsr()
graph = coo_matrix((weights, (cols, rows)), shape=(10, 10)).tocsr()

d1 = dijkstra(graph, indices=1, directed=True, unweighted=False)

#print(d1)

ans = 0

for i in range(H):
    a = [int(_) for _ in input().split()]
    for j in a:
        if j != -1:
            ans += d1[j]

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)]
r = [c[x][1] for x in range(10)] + [0]
done = [0]*10
done[1] = 1
ans = 0
while not all(done):
  mm = 10**5
  cur = -1
  for i in range(10):
    if not done[i] and r[i]<mm:
      mm = r[i]
      cur =  i
  done[cur] = 1
  for x in range(10):
    if r[x] > c[x][cur] + r[cur]:
      r[x] = c[x][cur] + r[cur]
for x in a:
  for y in x:
    ans += r[y]
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
INF = 2 ** 63 - 1
d = []
for i in range(10):
    d.append(list(map(int, input().split())))
A = []
for i in range(H):
    A += list(map(int, input().split()))
for k in range(10):
    for i in range(10):
        for j in range(10):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
ans = 0
for i in range(len(A)):
    if A[i] == -1:
        continue
    ans += d[A[i]][1]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce

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

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

A=Counter(map(int, reduce(lambda a,b: a+b, [input().split() for _ in range(H)])))
print(sum([c[i][1] * A[i] for i in range(10) if i in A]))

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

print(ans)

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
for _ in range(H):
	for x in input().split():
		x = int(x)
		if x != -1:
			ans += c[x][1]
print(ans)

Submission status: Accepted

Solution code:
class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  # d[u][v] : 辺uvのコスト(存在しないときはinf)

    def add(self, u, v, c, directed=False):
        """
        0-indexedであることに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        # これを d[i][j]: iからjへの最短距離 にする
        # TODO: verify in directed 本来無向グラフでのみ、全域木を考える
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        for i in range(self.N):
            self.d[i][i] = 0
        return self.d


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

graph = WarshallFloyd(10)
for i in range(10):
    for j in range(10):
        graph.add(i, j, C[i][j], directed=True)

d = graph.WarshallFloyd_search()

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import heapq
# 1までの距離を作成する。
# 逆向きに辺があると思って、1からの距離の一覧を作成

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

cost = np.zeros((10,10),dtype=np.int64)
for i in range(10):
  temp = map(int,input().split())
  for j,x in enumerate(temp):
    cost[j,i] = x

d = np.zeros(10,dtype=np.int64)

h = []
heapq.heappush(h,(0,1))
while h:
  dx,x = heapq.heappop(h)
  for y in range(10):
    if y in [1,x]:
      continue
    if d[y] == 0 or dx + cost[x,y] < d[y]:
      d[y] = dx+cost[x,y]
      heapq.heappush(h,(d[y],y))

answer = 0
for _ in range(H):
  row = input().split()
  for x in row:
    x = int(x)
    answer += 0 if x == -1 else d[x]
    
print(answer)

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]

n = [0]*10
for row in A:
    for a in row:
        if a != -1:
            n[a] += 1
n[1] = 0

def get_cost(n,tmp_cost = None):
    if cost[n] != None:
        return cost[n]
    if tmp_cost == None:
        tmp_cost = c[n][1]
    ret = tmp_cost
    for i in range(10):
        if i == n:
            continue
        if c[n][i] < tmp_cost:
            ret = min(ret,get_cost(i,tmp_cost-c[n][i])+c[n][i])
    if ret < tmp_cost:
        cost[n] = ret
    return ret

cost = [None]*10
cost[1] = 0
ans = 0
for i,ni in enumerate(n):
    if ni > 0:
        ans += ni * get_cost(i)
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)
decide=set()
INF=10**9
cost=[INF]*10
def check(cost):
    for i in cost:
        if i==INF:
            return True
    return False
while(check(cost)):
    l=-1
    m=INF
    for j in range(10):
        for i in range(10):
            if i in decide:
                continue
            c=min(C[i][1],C[i][j]+cost[j])
            if c<m:
                m=c
                l=i
    cost[l]=m
    decide.add(l)
ans=0
for i in range(H):
    A=list(map(int,input().split()))
    for j in A:
        if j==-1:
            continue
        ans+=cost[j]
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall as wf
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)]
C = wf(C)
cost = 0
for y in range(h):
    for x in range(w):
        if A[y][x] != -1:
            cost += C[A[y][x]][1]
print(int(cost))

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)]
INF = float('inf')
cost = 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])

for y in range(h):
    for x in range(w):
        if A[y][x] != -1:
            cost += C[A[y][x]][1]
print(cost)

Submission status: Accepted

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


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

d=warshall_floyd(c)
ans=0

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import heapq
import copy
import itertools

inf = float('inf')

class Graph_dijkstra(object):
    def __init__(self, V: "List[int]", E: "Set[Tuple[int, int]]", L: "Dict[Tuple[int, int], int]"):
        self.V = V
        self.E = E
        self.L = L
        self.adjacent = self.init_adjacent() # type: Dict[int: List[int]]
        self.shortest_path = self.init_shortest_path() # type: Dict[FrozenSet[int, int], int]
    
    def init_adjacent(self):
        ret = {v: [] for v in self.V}
        for e in self.E:
            ret[e[0]].append(e[1])
        return ret
    
    def init_shortest_path(self):
        ret = {(s, g): inf for s, g in itertools.permutations(self.V, 2)}
        for v in self.V:
            ret[(v, v)] = 0
        return ret
    
    def dijkstra(self, s: int):
        D = {v: inf for v in self.V}
        D[s] = 0
        prev = {v: None for v in self.V}
        Q = [(0, s)]

        while len(Q) > 0:
            du, u = heapq.heappop(Q)
            for v in self.adjacent[u]:
                e = (u, v)
                alt = du + self.L[e]
                if alt < D[v]:
                    D[v] = alt
                    prev[v] = u
                    heapq.heappush(Q, (D[v], v))

        for v in self.V:
            self.shortest_path[(s, v)] = D[v]

    def find_shortest_path(self, s: int, g:int):
        d = self.shortest_path[(s, g)]
        if d < inf:
            return d
        self.dijkstra(s)
        return self.shortest_path[(s, g)]


def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):
    V = list(range(10))
    E = set()
    L = dict()

    for i in range(10):
        for j in range(10):
            e = (i, j)
            E.add(e)
            L[e] = c[i][j]
    
    G = Graph_dijkstra(V, E, L)

    count = [0 for _ in range(10)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == -1:
                continue
            count[A[h][w]] += 1
    
    total = 0
    for i in range(10):
        total += G.find_shortest_path(i, 1) * count[i]

    print(total)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
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
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 or A[i][j] == 1:
            continue
        else:
            ans += c[A[i][j]][1]

print(ans)

Submission status: Accepted

Solution code:
#D問題

#warshall_floyd法
def warshall_floyd(dist):
    #dist[i][j]: 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])
    return dist

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

dist = [[float("inf") for i in range(10)] for i in range(10)] 


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

#dist[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(10):
    j=0
    for j in range(10):
        dist[i][j]=c[i][j]

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

Submission status: Accepted

Solution code:
def warshall_floyd(v_count: int, matrix: list) -> list:
    """ ワーシャルフロイド
    v_count: 頂点数
    matrix: 隣接行列(到達不能はfloat("inf"))
    """
    for i in range(v_count):
        for j, c2 in enumerate(row[i] for row in matrix):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix


H, W = map(int, input().split())
wall = [list(map(int, input().split()))for _ in range(10)]
mat = warshall_floyd(10, wall)
ans = 0
for i in range(H):
    for n in map(int, input().split()):
        if n == -1:
            continue
        ans += mat[n][1]
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from operator import add
from collections import Counter

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)]
A = reduce(add, A)
c = Counter(A)

class WarshallFloyd():
  def __init__(self, matrix):
    self.inf = 1e12
    self.v = len(matrix)
    self.e = matrix
    self.K = [[self.inf]*self.v for _ in range(self.v)]
    self.newK = self.K.copy()
    self.calculated = False
    
  def calc(self):
    for k in range(self.v):
      for i in range(self.v):
        self.newK[i][k] = min([self.K[i][k], self.e[i][k]])
        self.newK[k][i] = min([self.K[k][i], self.e[k][i]])

      for i in range(self.v):
        for j in range(self.v):
          if i!=j and i!=k and j!=k:
            self.newK[i][j] = min([self.K[i][j], self.newK[i][k]+self.newK[k][j]])
      self.K = self.newK.copy()
    self.calculated = True
    return self.K
  
  def shortest_way(self,a,b):
    if not self.calculated:
      self.calc()
    return self.K[a][b]

wf = WarshallFloyd(C)
wf.calc()

answer = 0
for k,v in c.items():
  if k!=-1:
    answer += v * wf.shortest_way(k,1)
print(answer)

Submission status: Accepted

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

nums = 10

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

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

Submission status: Accepted

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

import numpy as np
inf = 10**3
C = np.full((10,10),inf,dtype = int)#C[from][to]
for x in range(10):
    for inp,y in zip(input().split(),range(10)):
        C[x][y] = inp
        
A = [list(map(int,input().split())) for _ in range(h)]

def warshallfloyd(lis):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if i != j and k != i and k != j:
                    C[i][j] = min(C[i][j],C[i][k]+C[k][j])
warshallfloyd(C)
ans = 0
for a in A:
    for aa in a:
        if aa != -1:
            ans += C[aa][1]
print(ans)

Submission status: Accepted

Solution code:
import collections
import copy

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 += list(map(int,input().split()))
A=[a for a in A if a!=-1 and a!=1]
cnt=collections.Counter(A)

inf=1<<60
best_cost=inf
def walk(place, cost, history):
    global best_cost
    if cost==0:
        best_cost=inf
    if place==1:
        best_cost=min(best_cost,cost)
        return cost
    ret=inf
    for i in range(10):
        if i in history:
            continue
        if i == place:
            continue
        if cost+c[place][i]>=best_cost:
            continue
        history2 = copy.copy(history)
        history2 += [i]
        #print(place,i,history)
        ret=min(ret,walk(i,cost+c[place][i],history+[i]))
    return ret

ans=0
for k,v in cnt.items():
    ans+=v*walk(k,0,[])
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import heapq
h, w = [int(item) for item in input().split()]
c = [[int(item) for item in input().split()] for _ in range(10)]
a = [[int(item) for item in input().split()] for _ in range(h)]
INF = 10**9

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.num = len(adj)
        self.dist = [INF] * self.num
        self.prev = [INF] * self.num
        self.q = []

    def reset(self):
        self.dist = [INF] * self.num
        self.prev = [INF] * self.num
        self.q = []

    def calc(self, start, goal=None):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest in range(self.num):
                cost = self.adj[src][dest]
                if cost != INF and self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
                    self.prev[dest] = src
        if goal is not None:
            return self.get_path(goal)
        else:
            return self.dist

    def get_path(self, goal):
        path = [goal]
        dest = goal

        while self.prev[dest] != INF:
            path.append(self.prev[dest])
            dest = self.prev[dest]
        return list(reversed(path))

dijk = Dijkstra(c)
costs = [0] * 10
for i in range(10):
    costs[i] = dijk.calc(i)[1]
    dijk.reset()

count = Counter()
for item in a:
    count.update(item)

ans = 0
for key in count.keys():
    if key >= 0:
        ans += count[key] * costs[key]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

def getlist():
    return list(map(int, input().split()))

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b, w):
        self.graph[a].append((b, w))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[s] = 0
        self.prev = defaultdict(lambda: None)

        self.Q = []
        heappush(self.Q, (self.dist[s], s))

        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, w in self.g[u]:
                alt = dist_u + w
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def s_d(self, goal):
        return self.dist[goal]

    def s_p(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

H, W = getlist()
c = []
for i in range(10):
    cl = getlist()
    c.append(cl)
A = []
for i in range(H):
    Al = getlist()
    A.append(Al)

g_a = Graph()
for i in range(10):
    for j in range(10):
        a, b, w = i, j, c[i][j]
        if a != b:
            g_a.add_edge(b, a, w)

d_a = Dijkstra(g_a, 1)

ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == -1:
            pass
        else:
            ans += d_a.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])
cnt=[]      
for i in range(10):
    res=0
    for j in range(h):
        res+=A[j].count(i)
    cnt.append(res)    
print(sum(cnt[i]*c[i][1] for i in range(10)))

Submission status: Accepted

Solution code:

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

c = [[] * 10] * 10

a = [[] * w] * h

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


for z in range(10):
    for y in range(10):
        for x in range(10):
            if c[y][x] > c[y][z] + c[z][x]:
                c[y][x] = c[y][z] + c[z][x]

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

e = 0
for y in range(h):
    for x in range(w):
        if a[y][x] != -1 and a[y][x] != 1:
            i = a[y][x]
            e += c[i][1]
print(e)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections
import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist



h, w = map(int, input().split())
c = [list(map(int, input().split())) for i in range(10)]
adj = [[] for _ in range(10)]
for i in range(10):
    for j in range(10):
        c_ = c[i][j]
        adj[i].append((c_, j))
a = []
for i in range(h):
    A = list(map(int, input().split()))
    for j in A:
        a.append(j)
ac = collections.Counter(a)
ans = 0
for i in ac:
    if i != -1:
        ans += dijkstra(adj, 10, i)[1] * ac[i]
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)]
inf = float('inf')
cost = 0
D = [[inf]*10 for i in range(10)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            D[i][j] = min(C[i][j],C[i][k]+C[k][j])
for 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])

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

print(cost)

Submission status: Accepted

Solution code:
import heapq
class edge:
    def __init__(self,to,cost):
        self.to=to
        self.cost=cost

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

for i in range(10):
    tmp=list(map(int,input().split()))
    for j in range(10):
        if(i!=j):
            G[i].append(edge(j,tmp[j]))
            #G[j].append(edge(i,tmp[j])) #無向グラフならこれも


ans=[0 for _ in range(10)]
for j in range(N):
    tmp=list(map(int,input().split()))
    for i in tmp:
        if(i!=-1):
            ans[i]+=1


def dijkstra(o):
    d=[float('inf') for i in range(10)]
    d[o]=0
    hq=[]
    prev=[[] for i in range(10)]
    heapq.heappush(hq,(0,o))
    while hq:
        p=heapq.heappop(hq)
        v=p[1]
        if(d[v]<p[0]):
            continue
        for i in G[v]:
            if(d[i.to]>d[v]+i.cost):
                d[i.to]=d[v]+i.cost
                prev[i.to]=prev[v]+[str(sorted([v,i.to]))]
                heapq.heappush(hq,(d[i.to],i.to))
    return d,prev

s=0
for i in range(len(ans)):
    if(ans[i]!=0):
        s+=dijkstra(i)[0][1]*ans[i]
print(s)

Submission status: Accepted

Solution code:
H,W = list(map(int,input().split()))

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


for i in range(10):
    for j in range(10):
        for k in range(10):
            c[j][k] = min(c[j][k], c[j][i]+c[i][k])
res=0
for i in range(H):
    for j in range(W):
        if(A[i][j]>=0):
            res+=c[A[i][j]][1]
print(res)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
C=[list(map(int,input().split())) for i in range(10)]
cost=[float('inf')]*10
cost[1]=0
check={1,}
while len(check)>0:
    now=check.pop()
    for i in range(10):
        if cost[i]>cost[now]+C[i][now]:
            cost[i]=cost[now]+C[i][now]
            check|={i,}
cost.append(0)
ans=0
for h in range(H):
    for a in map(int,input().split()):
        ans+=cost[a]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
c = []
a = []

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

def search(glaph, start, goal):
    MAX_VAL = 0x10000000
    g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            tmp_cost = glaph[now][i] + cost[now]
            if cost[i] > tmp_cost:
                cost[i] = tmp_cost
                prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    return cost[goal]

cost = []
for i in range(10):
    cost.append(search(c, i, 1))
sum = 0
for row in a:
    for element in row:
        if (element != -1):
            sum += cost[element]
print(sum)

Submission status: Accepted

Solution code:
import numpy as np

minDis = np.zeros((10,10),dtype = int)
minDis.fill(10**18)

edge = np.zeros((10,10),dtype = int)
for i in range(10):
    minDis[i][i] = 0

h,w = map(int,input().split())
mat = np.zeros((h,w),dtype = int)
for i in range(10):
    edge[i] = list(map(int,input().split()))
for i in range(h):
    mat[i] = list(map(int,input().split()))

for start in range(10):
    #shortest path
    dis = [10**18] *10
    points = set(range(10))
    dis[start] = 0
    
    while points:
        #find point with min dis
        md = 10**18+1
        idx = start
        for point in points:
            if dis[point] <md:
                md = dis[point]
                idx = point
        points.remove(idx)
        for neighbour in range(10):
            if neighbour == idx:
                continue
            dis[neighbour] = min(dis[neighbour],dis[idx]+edge[idx][neighbour])
    minDis[start] = dis
#print(minDis) 
res = 0
for i in range(h):
    for j in range(w):
        if mat[i][j] == -1:
            continue
        res += minDis[mat[i][j]][1]
print(res)