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:
def JOI14_B():
    N = I()
    A = [I()for _ in range(N)]
    A.extend(A)
    dp = [[0]*(N*2+1) for _ in range(N*2+1)]

    for j in range(N):
        for i in range(N*2-j):
            if (N-j)%2==1:
                dp[i][i+j] = max(dp[i+1][i+j]+A[i],dp[i][i+j-1]+A[i+j])
            else:
                if A[i]>A[i+j]:
                    dp[i][i+j] = dp[i+1][i+j]
                else:
                    dp[i][i+j] = dp[i][i+j-1]
    ans = 0
    for i in range(N):
        ans = max(ans,dp[i][i+N-1])
    print(ans)
    #print(dp)
    return

def square869120Contest1_G():
    def held_karp(dists,TL):
        # Copyright (c) 2016 Carl Ekerot
        """
        Implementation of Held-Karp, an algorithm that solves the Traveling
        Salesman Problem using dynamic programming with memoization.
        Parameters:
            dists: distance matrix
        Returns:
            A tuple, (cost, path).
        """
        n = len(dists)

        # Maps each subset of the nodes to the cost to reach that subset, as well
        # as what node it passed before reaching this subset.
        # Node subsets are represented as set bits.
        C = {}
        dp = defaultdict(int)

        # Set transition cost from initial state
        for k in range(1, n):
            C[(1 << k, k)] = (dists[0][k], 0)
            dp[(1 << k, k)] = 1

        # Iterate subsets of increasing length and store intermediate results
        # in classic dynamic programming manner
        for subset_size in range(2, n):
            for subset in itertools.combinations(range(1, n), subset_size):
                # Set bits for all nodes in this subset
                bits = 0
                for bit in subset:
                    bits |= 1 << bit
                shortest_length = inf
                # Find the lowest cost to get to this subset
                for k in subset:
                    prev = bits & ~(1 << k)

                    res = []
                    for m in subset:
                        if not (prev, m) in C:
                            continue
                        if m == 0 or m == k:
                            continue
                        if C[(prev, m)][0] + dists[m][k]>TL[m][k]:
                            continue
                        res.append((C[(prev, m)][0] + dists[m][k], m))
                        if shortest_length>C[(prev, m)][0] + dists[m][k]:
                            shortest_length = C[(prev, m)][0] + dists[m][k]
                    if not res:
                        continue
                    C[(bits, k)] = min(res)
                    for d,m in res:
                        if shortest_length!=d:
                            continue
                        dp[(bits, k)] += dp[(prev,m)]

        # We're interested in all bits but the least significant (the start state)
        bits = (2 ** n - 1) - 1

        # Calculate optimal cost
        res = []
        shortest_length = inf
        for k in range(1, n):
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            res.append((C[(bits, k)][0] + dists[k][0], k))
            if shortest_length > C[(bits, k)][0] + dists[k][0]:
                shortest_length = C[(bits, k)][0] + dists[k][0]
        if not res:
            return False
        opt, parent = min(res)
        way = 0
        for d, k in res:
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            if shortest_length < d:
                continue
            way += dp[(bits,k)]

        # Backtrack to find full path
        path = []
        for i in range(n - 1):
            path.append(parent)
            new_bits = bits & ~(1 << parent)
            _, parent = C[(bits, parent)]
            bits = new_bits

        # Add implicit start state
        path.append(0)

        return shortest_length, list(reversed(path)), way

    N, M = LI()
    dist = [[inf]*N for _ in range(N)]
    TL = [[0]*N for _ in range(N)]
    for _ in range(M):
        s, t, d, time = LI()
        s -= 1; t -= 1
        dist[s][t] = dist[t][s] = d
        TL[s][t] = TL[t][s] = time
    ans = held_karp(dist,TL)
    if (not ans) or ans[2]==0:
        print("IMPOSSIBLE")
        return
    print(ans[0],ans[2])
    return

def JOI13_D():
    def solve(yday,leader,next):
        a = [0]*3
        for i in range(3):
            if next&(1<<i)==(1<<i):
                a[i] = 1
        rep = 0
        if a[leader]==0:
            return rep
        for i in range(3):
            if yday&(1<<i)==(1<<i):
                if a[i]==1:
                    rep = 1
        return rep
    N = I()
    S = SI()
    member = {"J":0,"O":1,"I":2}
    dp = [[0]*8 for _ in range(N+1)]
    dp[0][1] = 1
    for i in range(N):
        leader = member[S[i]]
        for j in range(8):
            for k in range(8):
                dp[i+1][j] += (dp[i][k]*solve(k,leader,j))
    ans = sum(dp[-1])%10007
    #print(dp)
    print(ans)
    return

def JOI16_D():
    N, M = LI()
    A = [(I()-1)for _ in range(N)]
    imos = [[0] * (N + 1) for _ in range(M)]
    for i in range(M):
        for j in range(N):
            imos[i][j + 1] += imos[i][j] + (A[j] != i)
    cnt = Counter(A)
    dp = [10 ** 9] * (1 << M)
    num = [None] * (1 << M)
    dp[0] = 0
    num[0] = 0
    for b in range(1 << M):
        for i in range(M):
            if b & (1 << i):
                continue
            nb = b | (1 << i)
            if num[nb] is None:
                num[nb] = num[b] + cnt[i]
            l = num[b]
            r = l + cnt[i]
            d = imos[i][r] - imos[i][l]
            dp[nb] = min(dp[nb], dp[b] + d)

    print(dp[-1])
    return

def ABC6_D():
    N = I()
    C = [I() for _ in range(N)]
    LIS = [C[0]]
    for i in range(N):
        if C[i] > LIS[-1]:
            LIS.append(C[i])
        else:
            LIS[bisect.bisect_left(LIS, C[i])] = C[i]
    print(N - len(LIS))
    return

def ABC134_E():
    N = I()
    A = [I()for _ in range(N)]
    que = deque()
    que.append(A[0])
    L = 1
    for i in range(1,N):
        cur = bisect.bisect_left(que,A[i])
        #print(que,cur,L)
        if cur==0:
            que.appendleft(A[i])
            L += 1
        else:
            que[cur-1] = A[i]

    #print(que)
    ans = len(que)
    print(ans)

    return

def JOI7_F():
    def dijkstra_2(edge_adj, node, start):
        # node<=2000くらい
        # edge_adj[node][to] = [cost]
        dist = [inf] * node
        used = [False] * node
        dist[start] = 0
        while True:
            v = -1
            for i in range(node):
                if not used[i] and (v == -1 or dist[v] > dist[i]):
                    v = i
            if v == -1:
                break
            used[v] = True
            for i in range(node):
                if dist[i] > dist[v] + edge_adj[v][i]:
                    dist[i] = dist[v] + edge_adj[v][i]
        return dist
    N, K = LI()
    V = [[inf]*N for _ in range(N)]
    ans = []
    for _ in range(K):
        A = LI()
        s = A[1]-1
        t = A[2]-1
        if A[0]==1:
            if V[s][t] <= A[3]:
                continue
            V[s][t] = A[3]
            V[t][s] = A[3]
        else:
            dist = dijkstra_2(V,N,s)
            ans.append(dist[t])
    for v in ans:
        if v==inf:
            print(-1)
            continue
        print(v)
    return

def JOI15_E():
    def bfs(n, E, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [inf] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        que = deque()
        for e in E:
            e -=1
            W[e] = 0
            que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] > nowW + 1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W

    class Dijkstra(object):
        """
        construct: O(ElogV)
        """

        def __init__(self, edges, start=0):
            """
            :param list of list of list of int edges:
            :param int start=0:
            """
            self.__dist = [inf] * len(edges)
            self.__dist[start] = 0
            self.__calculate(edges, start)

        @property
        def dist(self):
            return self.__dist

        def __calculate(self, edges, start):
            Q = [(0, start)]  # (dist,vertex)
            while (Q):
                dist, v = heapq.heappop(Q)
                if self.dist[v] < dist: continue  # 候補として挙がったd,vだが、他に短いのがある
                for u, cost in edges[v]:
                    if self.dist[u] > self.dist[v] + cost:
                        self.__dist[u] = self.dist[v] + cost
                        heapq.heappush(Q, (self.dist[u], u))
    N, M, K, S = LI()
    P, Q = LI()
    C = [I()for _ in range(K)]
    V = [[]for _ in range(N)]
    for _ in range(M):
        s, t = LI()
        s -= 1
        t -= 1
        V[s].append(t)
        V[t].append(s)
    L = bfs(N,C,V)
    #print(L)
    cost = [[]for _ in range(N)]
    for i in range(N):
        for v in V[i]:
            if L[v]==0:
                continue
            elif L[v]<=S:
                cost[i].append((v,Q))
            else:
                cost[i].append((v,P))
    di = Dijkstra(cost)
    ans = di.dist
    #print(cost)
    if L[-1]<=S:
        print(ans[N-1]-Q)
    else:
        print(ans[N-1]-P)
    return

def JOI13_E():
    def bfs(n, e, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [inf] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == inf:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W

    def dijkstra_2(edge_adj, node, start):
        # node<=2000くらい
        # edge_adj[node][to] = [cost]
        dist = [inf] * node
        used = [False] * node
        dist[start] = 0
        while True:
            v = -1
            for i in range(node):
                if not used[i] and (v == -1 or dist[v] > dist[i]):
                    v = i
            if v == -1:
                break
            used[v] = True
            for i in range(node):
                if dist[i] > dist[v] + edge_adj[v][i]:
                    dist[i] = dist[v] + edge_adj[v][i]
        return dist
    N, K = LI()
    C = [[]for _ in range(N)]
    V = [[]for _ in range(N)]
    for i in range(N):
        C[i] = LI()
    for i in range(K):
        a, b = LI()
        a -= 1
        b -= 1
        V[a].append(b)
        V[b].append(a)
    costV = [[inf]*N for _ in range(N)]
    for i in range(N):
        L = bfs(N,i,V)
        c = C[i][0]; l = C[i][1]
        for j in range(N):
            if i==j:
                continue
            if L[j]<=l:
                costV[i][j] = c
    dist = dijkstra_2(costV,N,0)
    ans = dist[N-1]
    #print(costV)
    print(ans)
    return

def ABC12_D():
    def warshall_floyd(n, 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
    N, M = LI()
    V = [[inf]*N for _ in range(N)]
    for i in range(N):
        V[i][i] = 0
    for _ in range(M):
        a, b, t = LI()
        a -= 1
        b -= 1
        V[a][b] = t
        V[b][a] = t
    L = warshall_floyd(N,V)
    #print(L)
    ans = inf
    for i in range(N):
        cur = max(L[i])
        ans = min(ans,cur)
    print(ans)
    return

def ABC79_D():
    def warshall_floyd(n, 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
    H, W = LI()
    C = [LI()for _ in range(10)]
    A = [LI()for _ in range(H)]
    L = warshall_floyd(10,C)
    #print(L)
    ans = 0
    for a in A:
        for i in a:
            if i>=0:
                ans += L[i][1]
    print(ans)
    return



def square869120Contest1_E():
    N, Q = LI()
    A = LI()
    C = LI()
    C.append(1)
    L = [0]*N
    for i in range(1,N):
        L[i] = pow(A[i-1],A[i],mod) + L[i-1]
    #print(L)
    ans = 0
    now = 0
    for i in range(Q+1):
        next = C[i]-1
        cur = abs(L[next]-L[now])
        ans += cur
        ans %= mod
        now = next
        #print(ans)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque

import gc
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    ABC79_D()
"""

"""

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from scipy.sparse import csr_matrix
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)]

g = csr_matrix(c)
dist = floyd_warshall(g)

ans = 0
for row in a:
    for e in row:
        if e == -1:
            continue

        else:
            ans += dist[e][1]

ans = int(ans)
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

H, W = [int(x) for x in input().strip().split()]
C = [0 for _ in range(10)]
for i in range(10):
    C[i] = [int(x) for x in input().strip().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]
                isChanged = True

ans = 0
for h in range(H):
    W = [int(x) for x in input().strip().split()]
    for w in W:
        if w == -1:
            continue
        ans += C[w][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)]

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

Submission status: Accepted

Solution code:
import heapq
import sys

H, W = map(int, input().split())
c = [[int(j) for j in input().split()] for i in range(10)]
A = [[int(j) for j in input().split()] for i in range(H)]
ans = 0
for i in A:
	for j in i:
		if j == -1:
			continue
		a = [(0, j)]
		b = [False] * 10
		d = [sys.maxsize] * 10
		d[j] = 0
		while len(a):
			e = heapq.heappop(a)
			b[e[1]] = True
			for k in range(len(c[e[1]])):
				if b[k]:
					continue
				if d[e[1]] + c[e[1]][k] < d[k]:
					d[k] = d[e[1]] + c[e[1]][k]
					heapq.heappush(a, (d[k], k))
		ans += d[1]
print(ans)

Submission status: Accepted

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

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

    N = 10
    cost = warshall_floyd(c)
    ans = 0

    for i in A:
        for j in i:
            if j >= 0:
                ans += cost[j][1]

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

N = 10
cost = warshall_floyd(c)
ans = 0

for i in A:
    for j in i:
        if j >= 0:
            ans += cost[j][1]

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import permutations

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

cost = []
for i in range(10):
    tmp = 10 ** 10
    factor = [int(x) for x in range(10) if x != i]
    per = list(permutations(factor))
    for j in per:
        a = [i] + list(j)
        cnt = 0
        for k in range(9):
            if a[k + 1] != 1:
                cnt += c[a[k]][a[k + 1]]
            else:
                cnt += c[a[k]][a[k + 1]]
                tmp = min(tmp, cnt)
                break
    cost.append(tmp)
ans = 0
for i in A:
    for j in i:
        if j != 1 and j != -1:
            ans += cost[j]
print(ans)

Submission status: Accepted

Solution code:
from itertools import chain
from collections import Counter

H, W = map(int, input().split())
dpCost = [list(map(int, input().split())) for _ in range(10)]
area = [list(map(int, input().split())) for _ in range(H)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            dpCost[i][j] = min(dpCost[i][j], dpCost[i][k]+dpCost[k][j])
wall = Counter(chain.from_iterable(area))
ans = 0
for k, v in wall.items():
    if k == 1 or k == -1:
        continue
    ans += v * dpCost[k][1]
print(ans)

Submission status: Accepted

Solution code:
def main():
    h, w = map(int, 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)]

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

    ret = 0
    for row in a:
        for cell in row:
            if ~cell:
                ret += c[cell][1]

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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


A = [list(map(int, input().split())) for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] != -1:
            ans += dist_list[A[i][j]][1]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
mod=10**9+7

def main():
    H,W=MI()
    c=[[] for _ in range(10)]
    A=[[] for _ in range(H)]
    
    for i in range(10):
        c[i]=LI()
    for i in range(H):
        A[i]=LI()
        
    def warshall_floyd(d):
        #d[i][j]: iからjへの最短距離
        n=10
        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
    
    c=warshall_floyd(c)
    
    ans=0
    for i in range(H):
        for j in range(W):
            if A[i][j]==-1:
                continue
            else:
                ans+=c[A[i][j]][1]
                
    print(ans)
            
    
    

main()

Submission status: Accepted

Solution code:



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

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


for k in range(10):
    for i in range(10):
        for j in range(10):
            convert[i][j] = min(convert[i][j], convert[i][k] + convert[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] not in [-1,1]:
            ans += convert[A[i][j]][1]

print(ans)

Submission status: Accepted

Solution code:
def main():
    H,W = list(map(int,input().split()))
    magic = [list(map(int,input().split())) for i in range(10)]
    wall = [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):
                magic[i][j] = min(magic[i][j],magic[i][k]+magic[k][j])
    
    ans = 0
    for h in range(H):
        for w in range(W):
            if wall[h][w] != -1:
                ans += magic[wall[h][w]][1]
    print(ans)
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue

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

change_list=[]
for i in range(10):
    if i==1:
        change_list.append(0)
    else:
        MIN=c[i][1]
        sub=queue.Queue()
        for g in range(10):
            if i!=g and g!=1 and c[i][g]<c[i][1]:
                sub.put((g,c[i][g]))
        while not sub.empty():
            now,_sum=sub.get()
            MIN=min(_sum+c[now][1],MIN)
            for l in range(10):
                if now!=l and l!=1 and _sum+c[now][l]<MIN:
                    sub.put((l,_sum+c[now][l]))
        change_list.append(MIN)

ans=0
for g in range(H):
    a=list(map(int,input().split()))
    for l in range(W):
        if a[l]!=-1:
            ans+=change_list[a[l]]

print(ans)

Submission status: Accepted

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

H,W = map(int, input().split())
C = []
for i in range(10):
	C.append([int(x) for x in input().split()])
C = warshall_floyd(10,C)
A = []
for i in range(H):
	A.append([int(x) for x in input().split()])

ans = 0
for i in range(H):
	for j in range(W):
		a = A[i][j]
		if a<0:
			continue
		ans += C[a][1]
print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd(d, n):
    # 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


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

d = warshall_floyd(c, n)

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

Submission status: Accepted

Solution code:
# 壁の各マスは独立に扱ってよいので、2→1、3→1、……の最低コストを求めればよい。
# https://qiita.com/e869120/items/eb50fdaece12be418faa だとワーシャル・フロイドの項に挙がっているが、
# ダイクストラだとダメなのかな?
# →ダイクストラは「ある1つの始点から、他のすべての点までの最短距離」をO(E log V)で計算する。
# 今回は始点が 1以外の9点なので、ダイクストラには向かない
# （2→3と3→2のコストは同じではないので、1から他のすべての点までを計算するのは不可。
# ダイクストラでも計算コスト上はできる。ダイクストラを9回やる羽目になるけど。）


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

v = 10

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

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

warshall_floyd(d, v)

ans =0
for i in range(h):
    for j in range(w):
        num = wall[i][j]
        if num == -1:
            pass
        else:
            # num → 1 の距離はc_{num, 1}
            ans += d[num][1]

print(ans)

Submission status: Accepted

Solution code:
#13:57
h,w = map(int,input().split())
inf = 10**9
wf = []
for i in range(10):
  wf.append(list(map(int,input().split())))
for k in range(10):
  for i in range(10):
    for j in range(10):
      wf[i][j] = min(wf[i][j],wf[i][k]+wf[k][j])
z1 = []
for i in range(10):
  z1.append(wf[i][1])
cnt = [0 for _ in range(10)] 
for _ in range(h):
  tmp = list(map(int,input().split()))
  for y in range(w):
    if tmp[y] != -1:
      cnt[tmp[y]] += 1
ans = 0
for i in range(10):
  ans += z1[i] * cnt[i]
#print(wf)
#print(z1)
#print(cnt)
print(ans)

Submission status: Accepted

Solution code:
import copy

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

num_dict = {}
for i in range(-1,10):
    new = {i:0}
    num_dict.update(new)

for i in range(h):
    A = list(map(int, input().split()))
    for a in A:
        num_dict[a] += 1

DP = copy.deepcopy(C)

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

ans = 0
for m in range(0, 10):
    ans += DP[m][1] * num_dict[m]

print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
# 多次元配列を作成する
def make_multi_list(initial, degree):
    ans = [initial for _ in range(degree[-1])]
    for d in reversed(degree[:-1]):
        ans = [deepcopy(ans) for _ in range(d)]
    return ans


H, W = map(int, input().split())
C = []
INF = float('inf')
dist = make_multi_list(INF, [10, 10])

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

# ワーシャルフロイド
for i in range(10):
    for j in range(10):
        dist[i][j] = C[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 n in map(int, input().split()):
        if n == -1:
            continue
        ans += dist[n][1]

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int,input().split())
dp = [[None]*10 for _ in range(10)]
for i in range(10):
    ls = list(map(int,input().split()))
    for j in range(10):
        dp[i][j] = ls[j]
from collections import defaultdict
d = defaultdict(int)
for i in range(H):
    for a in map(int,input().split()):
        d[a] += 1
for k in range(10):
    for i in range(10):
        for j in range(10):
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
ans = 0
for i in range(10):
    if i == 1:
        continue
    ans += dp[i][1]*d[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)]

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:
h, _ = map(int, input().split())
d = [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):
            d[i][j] = min(d[i][j], d[i][k]+d[k][j])

ans = 0
for aa in A:
    for a in aa:
        if a != -1:
            ans += d[a][1]

print(ans)