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:
INF=10**18
n=10
h,w=map(int,input().split())
dist=[list(map(int,input().split())) for _ in range(n)]
a=[list(map(int,input().split())) for _ in range(h)]
for k in range(n):
  for i in range(n):
    for j in range(n):
      dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
ans=0
for i in range(h):
  for j in range(w):
    if a[i][j]==-1:continue
    ans+=dist[a[i][j]][1]
print(ans)

Submission status: Accepted

Solution code:
import sys

H, W = map(int, input().split())
C = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(10)]
A = [list(map(int, sys.stdin.readline().rsplit())) 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]

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:
f=lambda:[*map(int,input().split())]
h,w=f()
r=range(10)
c=[f() for _ in r]
C=[0]*10
for _ in range(h):
  for i in f():
    if i>=0: C[i]+=1
for k in r:
  for i in r:
    for j in r:
      c[i][j]=min(c[i][j],c[i][k]+c[k][j])
print(sum(c[i][1]*C[i] for i in r))

Submission status: Accepted

Solution code:
f=lambda:[*map(int,input().split())]
h,w=f()
r=range(10)
c=[f() for _ in r]
C=[0]*10
for _ in range(h):
  for i in f():
    if i>=0: C[i]+=1
m=[c[i][1] for i in r]
for _ in r:
  for i in r:
    for j in r:
      m[i]=min(m[i],c[i][j]+m[j])
print(sum(m[i]*C[i] for i in r))

Submission status: Accepted

Solution code:
from collections import Counter
h, w = map(int, input().split())
C = [[0]*10 for _ in range(10)]
cost = []
for i in range(10):
    C[i] = 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])
costs = [C[i][1] for i in range(10)]

A = Counter()
for i in range(h):
    A += Counter(list(map(int,input().split())))

ans = 0
for key, val in A.items():
    if key!=-1:
        ans += val*costs[key]
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

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

    res = 0
    for h in range(H):
        for w in range(W):
            if grid[h][w] == -1 or grid[h][w] == 1:
                continue
            num = grid[h][w]
            res += cost[num][1]
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(10):
        for i in range(10):
            for j in range(10):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

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

d = [[float("inf")]*10 for i in range(10)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(10):
    l = list(map(int,input().split()))
    for j in range(10):
      d[i][j] = l[j]

a = [list(map(int,input().split())) for i in range(h)]
d1 = []
s = warshall_floyd(d)
for i in s:
  d1.append(i[1])
#print(d1)
su = 0
for i in a:
  for j in i:
    if j!=-1:
      su += d1[j]
print(su)

Submission status: Accepted

Solution code:
def warshall_floyd():
    '''
    すべての頂点間の最短距離を求める
    '''
    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])


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

warshall_floyd()

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:
from heapq import heappush, heappop


def dijkstra(s):
    '''
    始点sから各頂点への最短距離を求める
    '''
    d = [float("inf")] * 10
    d[s] = 0
    used = [False] * 10
    used[s] = True
    edgelist = []

    for e in edge[s]:
        heappush(edgelist, e)

    while edgelist:
        cost, v = heappop(edgelist)
        if used[v]:
            continue
        d[v] = cost
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(edgelist, [e[0] + d[v], e[1]])

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

edge = [[] for _ in range(10)]
for i in range(10):
    for j in range(10):
        edge[i].append([c[i][j], j])
        edge[j].append([c[j][i], i]) 

dist = []
for i in range(10):
    dist.append(dijkstra(i))

res = 0
for i in range(h):
    for j in range(w):
        if a[i][j] >= 0:
            res += dist[a[i][j]][1]

print(res)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
 
H, W, *t = map(int, open(0).read().split())
c = np.array(t[:100]).reshape((10, 10))
A = np.array(t[100:])
print(int(np.sum(shortest_path(c)[:, 1][A[A >= 0]])))

Submission status: Accepted

Solution code:
from numpy import *
from scipy.sparse.csgraph import *
H,W,*t=map(int,open(0).read().split())
c=array(t[:100]).reshape((10,10))
A=array(t[100:])
print(int(sum(shortest_path(c)[:,1][A[A>=0]])))

Submission status: Accepted

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

H, W, *t = map(int, open(0).read().split())
c = np.array(t[:100]).reshape((10, 10))
A = np.array(t[100:])
print(int(np.sum(shortest_path(c)[:, 1][A[A >= 0]])))

Submission status: Accepted

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

nums = [0 for _ in range(10)]

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

ans = 0
for i in range(H):
    for num in list(map(int, input().split())):
        if num == -1:
            continue
        else:
            ans += costs[num][1]

print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall, csgraph_from_dense
import sys
input = sys.stdin.readline

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 = csgraph_from_dense(c)
d = floyd_warshall(G).astype(int)

ans = 0

for l in a:
    for ai in l:
        if ai == -1:
            continue
        ans += d[ai][1]

print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd():
    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])

H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(10)]
warshall_floyd()
res = 0
for _ in range(H):
    A = list(map(int, input().split()))
    res += sum(C[a][1] for a in A if a != -1)
print(res)

Submission status: Accepted

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

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), *ca = [list(map(int, l.split())) for l in open(0)]

ccc = ca[:10]
aaa = ca[10:]

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

costs = [cc[1] for cc in ccc]

tmp = 0
for aa in aaa:
    for a in aa:
        if a == -1:
            pass
        else:
            tmp += costs[a]

print(tmp)

Submission status: Accepted

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

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


d=[0]*10
for start in range(10):

    #距離格納配列
    distance=grid[start]

    #確定済み配列
    visited=[0] * 10
    visited[start] = 1
    size = 1

    while size<10:
        min_distance = 10**9
        for i in range(10):
            if visited[i]==0 and distance[i] <min_distance:
                min_distance = distance[i]
                v = i

        visited[v] = 1
        size+=1

        for x in range(10):
            if distance[x] > distance[v] + grid[v][x]:
                distance[x] = distance[v] + grid[v][x]

    d[start]=distance[1]

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
INF = 10**10


def dijkstra(s, G):
    d = [INF] * len(G)
    d[s] = 0
    q = []
    heapq.heapify(q)
    heapq.heappush(q, (0, s))
    while len(q) > 0:
        shortest, v = heapq.heappop(q)
        if d[v] < shortest:
            continue
        for e in G[v]:
            to, cost = e
            if d[to] > d[v] + cost:
                d[to] = d[v] + cost
                heapq.heappush(q, (d[to], to))
    return d


H, W = map(int, input().split())
G = [[] for _ in range(10)]
for i in range(10):
    adj = list(map(int, input().split()))
    for j, cost in enumerate(adj):
        # 1からの距離を計算したいから逆向きのグラフを考える
        G[j].append((i, cost))
shortest_d = dijkstra(1, G)
ans = 0
for _ in range(H):
    for x in list(map(int, input().split())):
        if x == -1:
            continue
        ans += shortest_d[x]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
INF = 10**10

def dijkstra(n, edges, s):
    """
    input
        n : 頂点数
        edges : リスト(始点, 終点, コスト)
        s : 始点
    output
        d : 始点からの最短距離
    """
    d = [INF] * n
    used = [False] * n
    d[s] = 0
    used[s] = True
    edgelist = []
    # 初期のやつ
    for v, c in edges[s]:
        # print("v{},c{}".format(v,c))
        # コストを前にしてpushしておく(そこから最小値を取り出すので)
        heapq.heappush(edgelist, (c, v))
    # 空になるまで
    while len(edgelist):
        # コスト最小値を取り出す
        c_min, v_min = heapq.heappop(edgelist)
        # そのエッジがすでに確定していたら終わり
        if used[v_min]:
            continue
        # 確定していなければ、そこから派生するエッジをコスト付与して与える
        d[v_min] = c_min
        used[v_min] = True
        for v, c in edges[v_min]:
            if not used[v]:
                heapq.heappush(edgelist, (c+c_min, v))
    return d
h,w = map(int, input().split())
cij = []
for i in range(10):
    row = list(map(int, input().split()))
    cij.append(row)
A = []
for i in range(h):
    row = list(map(int, input().split()))
    A.append(row)
edges = [[] for i in range(10)]
for i in range(10):
    for j in range(10):
        if i != j:
            edges[i].append((j, cij[i][j]))

ds = []
for i in range(10):
    costs = dijkstra(10,edges,i)
    ds.append(costs[1])
ans = 0
for r in A:
    for e in r:
        if e == -1: continue
        ans += ds[e]
print(ans)

Submission status: Accepted

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

h, w = map(int, input().split())
graph = np.array([list(map(int, input().split())) for _ in range(10)])

cost = floyd_warshall(graph)
cost = cost.astype(int)

arr = np.array([list(map(int, input().split())) for _ in range(h)])
arr = arr.flatten()

ans = 0
for x in arr:
    if x == -1:
        continue
    else:
        ans += cost[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 i in map(int,input().split()):
        if i!=-1:
            ans+=c[i][1]
print(ans)

Submission status: Accepted

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


def warshall_floyd(A):
    #d[i][j]: iからjへの最短距離
    l = len(A)
    for k in range(l):
        for i in range(l):
            for j in range(l):
                A[i][j] = min(A[i][j], A[i][k] + A[k][j])
    return A


def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):
    c = warshall_floyd(c)
    cost = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] != -1:
                cost += c[A[h][w]][1]
    print(cost)
    return


# Generated by 1.1.7.1 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)]

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:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    import networkx as nx
    h, w = map(int, readline().split())
    G = nx.DiGraph()

    for i in range(10):
        costs = list(map(int, readline().split()))
        for j, cost in enumerate(costs):
            if i != j:
                G.add_edge(i, j, weight=cost)

    d = nx.algorithms.floyd_warshall(G)

    counter = Counter()
    for _ in range(h):
        nums = list(map(int, readline().split()))
        counter.update(nums)
    ans = 0
    for num in range(10):
        ans += counter[num] * d[num][1]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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:
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


def warsharll_floyd(c):
    n = len(c)
    for k in range(n):  # iからjへ向かう途中に中継する頂点
        for i in range(n):  # 始点
            for j in range(n):  # 終点
                # 現時点のiからjへ向かうコスト と kを経由してjに向かうコストの小さい方
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])
    return c


def main():
    h, w = LI()
    c = LIR(10)
    a = LIR(h)
    # a[i][j]を1に変える最小コストを考える
    # costs[i] : i を 1 に変えるコスト
    costs = warsharll_floyd(c)
    ans = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] in {-1, 1}:
                continue
            else:
                ans += costs[a[i][j]][1]
    print(ans)


main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
dist = [list(map(int,input().split())) for i in range(10)]
dist.append([0]*10)
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(n):
  a = list(map(int,input().split()))
  for j in a:
    ans += dist[j][1]
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
# list(map(int, input().split()))

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

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

A = [0] * H
for i in range(H):
    A[i] = 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][k] + C[k][j], C[i][j])

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

Submission status: Accepted

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

mp=[[0]*10 for i 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])

a=[[] for i in range(h)]

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

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

ans = 0
for i in range(h):
    wall = list(map(int, input().split()))  
    for item in wall:
        if item < 0:
            continue
        ans += power[item][1]  
print(ans)

Submission status: Accepted

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

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

ans = 0
for i in range(h):
    wall = list(map(int, input().split()))  
    for item in wall:
        if item < 0:
            continue
        ans += power[item][1]  
print(ans)

Submission status: Accepted

Solution code:
# ABC079

import sys
input=sys.stdin.readline

def main():
    inf=10**6
    H,W=map(int,input().split())
    dp=[[inf]*10 for i in range(10)]
    for i in range(10):
        row=list(map(int,input().split()))
        for j in range(10):
            dp[i][j]=row[j]
    
    cnt=[0]*10
    for i in range(H):
        row=list(map(int,input().split()))
        for a in row:
            if a!=-1:
                cnt[a]+=1
                
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if dp[i][k]<inf and dp[k][j]<inf:
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
                    
    ans=0
    for i in range(10):
        ans+=dp[i][1]*cnt[i]
        
    print(ans)
    
                
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
from itertools import chain
from collections import Counter
def main():
    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

    h, w = map(int, input().split())
    n = 10
    d = [[10**9] * 10 for _ in range(10)]
    for i1 in range(10):
        row = tuple(map(int, input().split()))
        for i2 in range(10):
            d[i1][i2] = row[i2]
    res = warshall_floyd(d)
    hw = [list(map(int, input().split())) for _ in range(h)]
    hw1d = chain.from_iterable(hw)
    hw1dc = Counter(hw1d)
    r = 0
    for j1 in range(10):
        r += hw1dc[j1] * res[j1][1]
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
INF = 2**100

h, w = map(int, input().split())
n = 10
d = [[INF for i in range(n)] for j in range(n)]
for i in range(n):
    a = [int(i) for i in input().split()]
    for j in range(n):
        d[i][j] = a[j]
for i in range(n):
    d[i][i] = 0
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])

num = [0] * n
for i in range(h):
    b = [int(j) for j in input().split()]
    for j in b:
        if j != -1:
            num[j] += 1

print(sum([d[i][1]*num[i] for i in range(n)]))

Submission status: Accepted

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

H,W = map(int,readline().split())
G = [None] * 10

for i in range(10):
  G[i] = list(map(int,readline().split()))

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

ans = 0
for i in range(H):
  line = list(map(int,readline().split()))
  for j in range(W):
    if line[j] == -1:
      continue
    if line[j] == 1:
      continue
    ans += G[line[j]][1]

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc079/tasks/abc079_d

# cost[i][j] = 数字 i から数字 j に変えた時の最小コスト
# per[i][j] = 最小コストを実現した際の数字 i を数字 j に変えるのにかかるコスト
# num[i][j] = 最小コストを実現した際の新たに追加された数字 j の個数

from collections import Counter
from copy import copy

import sys
input = sys.stdin.readline

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

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

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

cnt = Counter(A)

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

res = 0
for i in range(10):
    res += cnt[i]*cost[i][1]


print(res)

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:
h,w=map(int,input().split())
ans=[float("inf") for i in range(10)]
p=[]
a=[]
for i in range(10):
    p.append(list(map(int,input().split())))
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):
            p[j][k]=min(p[j][i]+p[i][k],p[j][k])
ans=float("inf")
tmp=0
for j in range(h):
    for k in range(w):
        if a[j][k]!=-1:
            tmp+=p[a[j][k]][1]
print(tmp)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

nums = []
for _ in range(h):
    nums += [int(i) for i in input().split()]


def dijkstra(s=1, c=c):
    INF = float('inf')

    d = {i: INF for i in range(10)}
    d[-1] = 0
    d[s] = 0

    queue = []
    heappush(queue, (0, s))

    while queue:
        di, v = heappop(queue)
        for i in range(10):
            dtmp = d[v] + c[i][v]
            if dtmp < d[i]:
                d[i] = dtmp
                heappush(queue, (dtmp, i))

    return d


magic = dijkstra()
answer = sum(magic[i] for i in nums)
print(answer)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall, csgraph_from_dense

# 入力
H, W = map(int, input().split())
G = [[int(i) for i in input().split()] for j in range(10)]
G = csgraph_from_dense(G)

dist = floyd_warshall(G)
ans = 0
for h in range(H):
    line = [int(i) for i in input().split()]
    for w in range(W):
        if line[w] == -1:
            continue
        ans += dist[line[w]][1].astype(int)

print(ans)

Submission status: Accepted

Solution code:
def main():
    h, w, *ca = map(int, open(0).read().split())
    it = zip(*[iter(ca[:100])] * 10)
    *c, = map(lambda i: list(i), it)
    a = ca[100:]

    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
    cost = {i: c[i][1] for i in [0, 2, 3, 4, 5, 6, 7, 8, 9]}
    cost.update({-1: 0, 1: 0})

    for i in a:
        ans += cost[i]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    h, w, *ca = map(int, open(0).read().split())
    it = zip(*[iter(ca[:100])] * 10)
    *c, = map(lambda i: list(i), it)
    a = ca[100:]

    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
    cost = {i: c[i][1] for i in [0, 2, 3, 4, 5, 6, 7, 8, 9]}

    for i in a:
        if i in [-1, 1]:
            continue
        ans += cost[i]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    h, w, *ca = map(int, open(0).read().split())
    it = zip(*[iter(ca[:100])] * 10)
    *c, = map(lambda i: list(i), it)
    a = ca[100:]

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

    ans = 0

    for i in a:
        if i in [-1, 1]:
            continue
        ans += c[i][1]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
C = [tuple(map(int, input().split())) for _ in range(10)]
A = [tuple(map(int, input().split())) for _ in range(h)]
AtoOne = [1001 for i in range(10)]

from collections import deque
q = deque([[1, 0]])

while q:
    i, cost = q.popleft()
    if AtoOne[i] > cost:
        AtoOne[i] = cost
    else:
        continue

    for j in range(10):
        if i == j:
            continue
        q.append([j, cost + C[j][i]])

counts = [0] * 10
for i in range(h):
    for j in range(w):
        a = A[i][j]
        if a > -1:
            counts[a] += 1
ans = 0 
for from_i, c in enumerate(counts):
    ans += c * AtoOne[from_i]
print(ans)

Submission status: Accepted

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

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

def main(args):
    H,W = map(int,input().split())
    cost = [[0] for _ in range(10)]
    for i in range(10):
        cost[i] = list(map(int,input().split()))
    
    wall = [[] for _ in range(H)]
    for i in range(H):
        wall[i] = list(map(int,input().split()))
    
    warshallFloyd(10, cost)
    
    cost_to_one = [0]*10
    for i in range(10):
        cost_to_one[i] = cost[i][1]
    
    #print(cost_to_one)
      
    ans = 0
    for i in range(H):
        for j in range(W):
            if wall[i][j] != -1:
                ans += cost_to_one[wall[i][j]]
    
    print(ans)
    
if __name__ == '__main__':
    main(sys.argv[1:])