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:
from scipy.sparse.csgraph import floyd_warshall as wf

H,W = map(int,input().split())
C = [[int(i) for i in input().split()] for i in range(10)]
A = [[int(i) for i in input().split()] for i in range(H)]
B = wf(C)
ans = 0

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

print(int(ans))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
h,w = map(int,input().split())
cost = []
for i in range(10):
  sub = list(map(int,input().split()))
  cost.append(sub)
d = [[float("inf")]*10 for i in range(10)]
L = []
for i in range(10):
    d[i][i] = 0
for i in range(10):
    for j in range(10):
        d[i][j] = cost[i][j]
        d[j][i] = cost[j][i]
d = floyd_warshall(d)
wall = []
for i in range(h):
    cur = list(map(int,input().split()))
    wall.append(cur)
ans = 0
for i in range(h):
    for j in range(w):
        if wall[i][j] != -1:
            ans += d[wall[i][j],1]
print(int(ans))

Submission status: Accepted

Solution code:
def d_wall(H, W, C, A):
    import scipy.sparse
    # cost[i][j]:数字iからjに移行するための最小コスト(float64で格納される)
    cost = scipy.sparse.csgraph.floyd_warshall(C)
    # 壁の各数字ごとに、その数字から1へ変えるための最小コストを計算し、和を取る
    return int(sum(cost[A[h][w]][1] for h in range(H) for w in range(W) if A[h][w] != -1))

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[list(map(int,input().split()))for i in range(10)]
b=[list(map(int,input().split()))for i in range(h)]
for h in range(10):
    for i in range(10):
        for j in range(10):
            if a[i][j]>a[i][h]+a[h][j]:
                a[i][j]=a[i][h]+a[h][j]
print(sum([sum([a[d][1] if d>=0 else 0 for d in i])for i in b]))

Submission status: Accepted

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

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


sum_cost = 0
for i in range(H):
    num = [int(i) for i in input().split()]
    for n in num:
        if n != -1:
            sum_cost += cost[n][1]

print(sum_cost)

Submission status: Accepted

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

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

B = wf(C)

ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == -1:
            continue
        ans += B[A[i][j]][1]
        
print(int(ans))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    a,b,c,d = list(map(int, S()))
    s = ["-","+"]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                if eval(str(a)+s[i]+str(b)+s[j]+str(c)+s[k]+str(d)) == 7:
                    print(str(a)+s[i]+str(b)+s[j]+str(c)+s[k]+str(d)+"=7")
                    quit()
#D
def D():
    h,w = LI()
    d = [None for i in range(10)]
    for i in range(10):
        d[i] = LI()
    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(h):
        s = LI()
        for k in s:
            if k != -1:
                ans += d[k][1]
    print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

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

Submission status: Accepted

Solution code:
def warshall_floyed(n):
    global d
    for m in range(n):
        for s in range(n):
            for t in range(n):
                d[s][t] = min(d[s][t],
                              d[s][m] + d[m][t])
                
if __name__ == "__main__":
    H,W = map(int, input().split())
    d = [list(map(int, input().split())) for _ in range(10)]
    warshall_floyed(10)
    cnt = [0]*10
    for h in range(H):
        a = list(map(int, input().split()))
        for ai in a:
            if ai>-1:
                cnt[ai]+=1
    ans = 0
    for i in range(10):
        ans += cnt[i]*d[i][1]
    print(ans)

Submission status: Accepted

Solution code:
import heapq


class PriorityQueue:
    def __init__(self):
        self.__heap = []
        self.__count = 0

    def empty(self) -> bool:
        return self.__count == 0

    def dequeue(self):
        if self.empty():
            raise Exception('empty')
        self.__count -= 1
        return heapq.heappop(self.__heap)

    def enqueue(self, v):
        self.__count += 1
        heapq.heappush(self.__heap, v)

    def __len__(self):
        return self.__count


def dijkstra(s: int, t: int, V: int, edges: list) -> int:
    '''dijkstra method
    :param s: start
    :param t: finish
    :param V: number of vertexes
    :param edges: collection of edges
    :return: minimum distance from u to v
    '''
    d = [float('inf')] * V
    d[s] = 0

    q = PriorityQueue()
    q.enqueue((d[s], s))

    while not q.empty():
        _, u = q.dequeue()
        for v, cost in edges[u]:
            alt = d[u] + cost

            if alt < d[v]:
                d[v] = alt
                q.enqueue((d[v], v))

    return d[t]


def wall(H: int, W: int, C: list, A: list) -> int:
    # 1 から各数字への最短距離を計算する
    edges = [[(v, C[u][v]) for v in range(10)] for u in range(10)]
    min_dist = [dijkstra(i, 1, 10, edges) for i in range(10)]

    return sum(
        min_dist[a]
        for row in A
        for a in row if a >= 0)


if __name__ == "__main__":
    H = 0
    H, W = map(int, input().split())
    C = [[int(s) for s in input().split()] for _ in range(10)]
    A = [[int(s) for s in input().split()] for _ in range(H)]
    ans = wall(H, W, C, A)
    print(ans)

Submission status: Accepted

Solution code:
import sys

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


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

    d = warshall_floyd(C)

    ans = 0
    for a in A:
        for i in a:
            if i == -1:
                continue
            ans += d[i][1]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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

    dp = [[10**4] * 10 for _ in range(10)]
    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 a in A:
        for i in a:
            if i == -1:
                continue
            ans += C[i][1]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
	H, W = map(int, input().split(" "))
	MP = []
	for _ in range(10):
		tmp = input().split(" ")
		tmp = [int(s) for s in tmp]
		MP.append(tmp)
	
	MP = warshall_floyd(MP, 10)
	
	ans = 0
	for _ in range(H):
		tmp = input().split(" ")
		tmp = [int(s) for s in tmp]
		for i, val in enumerate(tmp):
			if val == -1:
				continue
			ans += MP[val][1]
		
	print(ans)
	
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
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from itertools import chain
from collections import Counter
H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(10)]
A = Counter(list(chain.from_iterable([list(map(int, input().split())) for _ in range(H)])))
for _ in range(100):
    for i in range(10):
        for j in range(10):
            c = min([C[i][k] + C[k][j] for k in range(10)])
            C[i][j] = min(c, C[i][j])
num = 0
for i, n in A.items():
    if i == -1:
        continue
    num += C[i][1] * n
print(num)

Submission status: Accepted

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


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

    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 x in range(h):
        for y in range(w):
            pos = a[x][y]

            if pos >= 0:
                ans += c[pos][1]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#ABC079C
import copy
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 DP(i,check,x):
    s=C[i][1]
    for c in range(10):
        if c!=i and check[c]!=1 and C[i][c]<C[i][1]:
            t=copy.deepcopy(check)
            t[c]=1
            s=min(s,C[i][c]+DP(c,t,x))
    return x+s
B=[0]*10
for i in range(10):
    if i!=1:
        B[i]=DP(i,[1 if t==1 or t==i else 0 for t in range(10)],0)
D=[0]*10
for h in range(H):
    for w in range(W):
        if A[h][w]!=-1:
            D[A[h][w]]+=1
print(sum([B[i]*D[i] for i in range(10)]))

Submission status: Accepted

Solution code:
def warshall_floyd(graph):
    dist = [[1e9 for i in range(10)] for k in range(10)]
    for i in range(10):
        dist[i][i] = 0
    for i in graph:
        for k in range(9):
            dist[i][graph[i][k][0]] = graph[i][k][1]
    for i in range(10):
        for k in range(10):
            for j in range(10):
                dist[k][j] = min(dist[k][j],dist[k][i] + dist[i][j])
    return dist


h,w = map(int,input().split())
graph = dict()
for i in range(10):
    graph[i] = []

for i in range(10):
    temp = list(map(int,input().split()))
    for k in range(10):
        if i != k:
            graph[i].append([k,temp[k]])
dist = warshall_floyd(graph)
a = []
ans = 0
for i in range(h):
    temp = list(map(int,input().split()))
    for k in range(w):
        if temp[k] > 1 or temp[k] == 0:
            ans += dist[temp[k]][1]
print(ans)

Submission status: Accepted

Solution code:
def wf(d):
    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)

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):
    for j in list(map(int,input().split())):
        if j == -1:
            continue
        if j not in A.keys():
            A[j] = 0
        A[j] += 1


d = wf(c)
ans = 0
for key in A.keys():
    if key != 1:
        ans += A[key]*d[key][1]

print(ans)

Submission status: Accepted

Solution code:
def wf(c):
    d = {}
    for i in range(10):
        for j in range(10):
            d[(i,j)] = c[i][j]
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if d[(i,j)] > d[(i,k)] + d[(k,j)]:
                    d[(i,j)] = d[(i,k)] + d[(k,j)]
    e = {}
    for i in range(10):
        e[i] = d[(i,1)]
    return e


def solve(H, W, c, A):
    d = wf(c)
    mp = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] != -1:
                mp += d[A[i][j]]
    return mp


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

    ans = solve(H, W, c, A)
    print(ans)



if __name__ == '__main__':
    main()

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)]
# djikstra
dis = [0] * 10
s = {1}
u = {0,2,3,4,5,6,7,8,9}
for i in range(10):
    dis[i] = cost[i][1]
for _ in range(10):
    if u == set():
        break
    mindis = 10**9
    for i in u:
        if dis[i] < mindis:
            a = i
            mindis = dis[i]
    u.remove(a)
    s.add(a)
    for i in u:
        dis[i] = min(dis[i], dis[a] + cost[i][a])
count = {}
for i in range(h):
    for j in range(w):
        if wall[i][j] >= 0:
            if wall[i][j] not in count:
                count[wall[i][j]] = 1
            else:
                count[wall[i][j]] += 1
ans = 0
for i, c in count.items():
    ans += dis[i] * c
print(ans)

Submission status: Accepted

Solution code:
# 078-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
h,w=IL()
c=[IL() for i in range(10)]
a=[IL() for i in range(h)]

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

Submission status: Accepted

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

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

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

for k in range(10):
  for i in range(10):
    for j in range(10):
      if cmap[i][j] > cmap[i][k] + cmap[k][j]:
        cmap[i][j] = cmap[i][k] + cmap[k][j]

ans = 0
for alist in amap:
  for a in alist:
    if a != -1:
      ans += cmap[a][1]

print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd(d):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
  
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

cost = warshall_floyd(c)

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

print(ans)

Submission status: Accepted

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


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

a_list = []
for i in range(H):
    a_list.append(tuple(map(int, input().split())))
graph = warshall_floyd(items)

ans = 0
for a in a_list:
    for item in a:
        if item == -1:
            continue
        ans += graph[item][1]
print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd(d, V): #d[i][j]は2頂点間i, j間の移動コストを格納, Vは頂点数
    for k in range(V):
        for i in range(V):
            for j in range(V):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
                
    return d
                
H, W = map(int, input().split())                
L = [list(map(int, input().split())) for _ in range(10)]
a = [list(map(int, input().split())) for _ in range(H)]

cost = warshall_floyd(L, 10)

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

Submission status: Accepted

Solution code:
import numpy as np
H, W = map(int, input().split())
mC = np.zeros((10, 10), dtype=int)
for i in range(10):
    mC[i] = list(map(int, input().split()))
A = []
for _ in range(H):
    A += list(map(int, input().split()))
from collections import Counter
cnt9 = Counter(A)
del cnt9[-1]
# Warshall-Floyd
for i in range(10):
    mC = np.minimum(mC, mC[i: i + 1] + mC[:, i: i + 1])

ans = 0
for i, cnt in cnt9.items():
    ans += mC[i, 1] * cnt

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
input = sys.stdin.readline
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
n = 10
h,w = map(int,input().split())
d = [[] for i in range(10)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(10):
    d[i] = list(map(int,input().split()))

d = warshall_floyd(d)

res = 0
for i in range(h):
    p = tuple(map(int,input().split()))
    for e in p:
        if e == -1:
            continue
        res += d[e][1]
print(res)

Submission status: Accepted

Solution code:
import itertools
H,W = map(int,input().split())
C = [list(map(int,input().split())) for i in range(10)]
bit = [0]*10
for i in range(H):
    s = input().split()
    for j in range(W):
        if int(s[j]) == -1: continue
        bit[int(s[j])] += 1

# dist[i][j]: iからjへのコスト,  n:頂点数
def warshall_floyd(dist,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k]+dist[k][j]:
                    dist[i][j] = dist[i][k]+dist[k][j]

warshall_floyd(C,10)
ans = 0
for i in range(10):
    ans += C[i][1]*bit[i]
print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
ij = [list(map(int,input().split())) for x in range(10)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            ij[i][j] = min(ij[i][j],ij[i][k]+ij[k][j])
ans = 0
for i in range(h):
    for j in list(map(int,input().split())):
        if j == -1:continue
        ans += ij[j][1]
print(ans)

Submission status: Accepted

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


from collections import defaultdict
d = defaultdict(int)

dist = [ [float("inf")] * 10 for _ in range(10)]
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] )


A = [ [int(j) for j in input().split()] for _ in range(H)]
for ai in A:
    for aij in ai:
        d[aij] += 1
ans = 0
for i in range(0,10):
    if i == 1: continue
    ans += d[i]* dist[i][1]
print(ans)

Submission status: Accepted

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

for i in range(H):
    a = list(map(int, input().split()))
    A[i] = 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])

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

print(num)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
inf = float("inf")
dp = [[inf]*100 for _ in [0]*100]
for i in range(10):dp[i][i] = 0
d = [list(map(int, input().split())) for i in range(10)]
m = [list(map(int, input().split())) for i in range(N)]
ans = 0
 
for i in range(10):
    for j in range(10):
        dp[i][j] = d[i][j]
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])
c=0
for i in range(N):
    for j in range(M):
        if m[i][j] != 1 :
            if m[i][j] != -1 :
                c+=dp[m[i][j]][1]
print(c)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
L = []
ans = 0
x,y = map(int,input().split())
for _ in range(10):
    l = list(map(int, input().split()))
    L.append(l)

def warshall_floyd(n,w,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

d = [[float("inf") for i in range(10)] for i in range(10)] 
for i in range(10):
    for j in range(10): 
        d[i][j] = L[i][j]
for i in range(10):
    d[i][i] = 0 #
w =  warshall_floyd(10,10,d)
for _ in range(x):
    s = list(map(int, filter(lambda x:x!="-1",input().split())))
    for x in s:
     
        ans += w[x][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)]
 
len_c = len(c)

#ワーシャルフロイド
for k in range(len_c):
  for i in range(len_c):
    for j in range(len_c):
      c[i][j] = min(c[i][j], c[i][k]+c[k][j])
 
ans =0
for i in range(h):
  for j in range(w):
    if a[i][j]==-1:
      ans += 0
    else:
      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 i in range(10)]
a = [list(map(int,input().split())) for i in range(h)]


#正方行列を読み込む

len_c = len(c)
cost = [[float('inf')]*len_c for i in range(len_c)]

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

ans =0
for i in range(h):
  for j in range(w):
    if a[i][j]==-1:
      ans += 0
    else:
      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)]

from itertools import product

for k,i,j in product(range(10),repeat=3):
    if c[i][j] > c[i][k]+c[k][j]:
        c[i][j] = c[i][k]+c[k][j]
ans=0

for i,j in product(range(H),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)]

mincost=[0 for i in range(10)]

for i in range(10):
    if i!=1:
        res = {i:0}
        path = [(j,c[i][j]) for j in range(10) if j not in res.keys()]
        while 1 not in res.keys():
            path.sort(key=lambda x:x[1])
            node,cost=path[0]
            res[node]=cost
            path = [p for p in path if p[0] not in res.keys()]
            path += [(j,cost+c[node][j]) for j in range(10) if j not in res.keys()]
        mincost[i]=res[1]

ans=0
from itertools import product
for i,j in product(range(H),range(W)):
    if A[i][j]!=-1:
        ans+=mincost[A[i][j]]
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
H,W = list(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)]

#i:始点 j:終点 k:経由する点
for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j] = min(c[i][j],c[i][k]+c[k][j])

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
class Graph(object):

    class Edge:
        def __init__(self, to: int, cost: int):
            self.to = to
            self.cost = cost

        def __str__(self):
            return "Edge: (to " + str(self.to) + ", cost " + str(self.cost) + ")"

        def __repr__(self):
            return self.__str__()

    INF = 10e10

    def __init__(self, node_n: int):
        self.node_n = node_n
        self.edges = [{} for _ in range(self.node_n)]
        self.dist = [self.INF for _ in range(self.node_n)]

    def set_edge(self, from_pos: int, to_pos: int, cost: int, reversible: bool) -> None:
        self.edges[from_pos][to_pos] = self.Edge(to_pos, cost)
        if reversible:
            self.edges[to_pos][from_pos] = self.Edge(from_pos, cost)

    def solve(self) -> list:
        raise NotImplementedError


class WarshallFloyd(Graph):
    def solve(self) -> None:
        for via_p in range(self.node_n):
            for from_p in range(self.node_n):
                for to_p in range(self.node_n):
                    if via_p in self.edges[from_p].keys() and to_p in self.edges[via_p].keys():
                        alt = self.edges[from_p][via_p].cost + self.edges[via_p][to_p].cost
                        if to_p not in self.edges[from_p]:
                            self.edges[from_p][to_p].cost = alt
                        else:
                            self.edges[from_p][to_p].cost = min(self.edges[from_p][to_p].cost, alt)


if __name__ == '__main__':
    H, W = map(int, input().split())
    graph = WarshallFloyd(10)

    for i in range(10):
        buff = [int(i) for i in input().split()]
        for j in range(10):
            graph.set_edge(i, j, buff[j], False)

    graph.solve()

    A = [[int(j) for j in input().split()] for _ in range(H)]
    ans = sum(map(lambda l:
                  sum(map(lambda e:
                          0 if e == -1 else graph.edges[e][1].cost
                          , l))
                  , A))
    print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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


def dijkstra(s, g):
    '''
        s:start node
        g:foal node
        return cost from s to g
    '''
    return 0


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


mp = war(mp)
cost = 0
for l in wall:
    for i in l:
        if i == -1:
            continue
        else:
            cost += mp[i][1]
print(cost)

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