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:
icase=0
if icase==0:
    h,w=map(int,input().split())
    dp=[[0]*10 for i in range(10)]
    for i in range(10):
        dp[i]=list(map(int,input().split()))
    a=[]
    for i in range(h):
        a.extend(list(map(int,input().split())))
elif icase==1:
    h,w=2,4
    dp=[[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]]

    a=[-1, -1, -1, -1, 8, 1, 1, 8]

from collections import Counter
ac=Counter(a)

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

icnt=0
for i in range(10):
    if ac[i]>0:
        icnt+=dp[i][1]*ac[i]  

print(icnt)

Submission status: Accepted

Solution code:
def main():
    inf=float("inf")
    h,w=map(int,input().split())
    lst=[list(map(int,input().split())) for _ in range(10)]
    dp1=[[inf]*10 for _ in range(10)]
    
    for i in range(10):
        for j in range(10):
            dp1[i][j]=lst[i][j]
    
    for k in range(1,11):
        dp2=[dp1[i][:] for i in range(10)]
        for i in range(10):
            for j in range(10):
                if dp2[i][j]>dp2[i][k-1]+dp2[k-1][j]:
                    dp1[i][j]=dp2[i][k-1]+dp2[k-1][j]

    wall=[list(map(int,input().split())) for _ in range(h)]
    sm=0
    for i in range(h):
        for j in range(w):
            if wall[i][j]==-1 : continue
            sm+=dp1[wall[i][j]][1]

    print(sm)
    
main()

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
import numpy as np

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W = map(int, readline().split())
    L = list(list(map(int, readline().split())) for _ in range(10))
    A = list(list(map(int, readline().split())) for _ in range(H))
    dist = dijkstra(csr_matrix(L))
    ans = 0
    for a in A:
        for i in a:
            if i == -1:
                continue
            else:
                ans += dist[i][1]
    print(int(ans))




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

V = 10

dists = []

for _ in range(V):
    dists.append(list(map(int, input().split())))

count = defaultdict(int)

for _ in range(H):
    for i in map(int, input().split()):
        count[i] += 1

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


ans = 0

for k, v in count.items():
    if k == -1 or k == 1:
        continue
    ans += v * dists[k][1]
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from heapq import heappop, heappush

    def input(): return sys.stdin.readline().rstrip()

    def dijkstra(s):
        inf = 10**6
        dist = [inf]*10
        dist[1] = 0
        que = [(0, 1)]
        while que:
            cost, node = heappop(que)
            if cost > dist[node]:
                continue
            for i in range(10):
                if i == node:
                    continue
                if dist[i] > dist[node] + g[i][node]:
                    dist[i] = dist[node]+g[i][node]
                    heappush(que, (dist[i], i))
        return dist
    
    h, w = map(int, input().split())
    g = [[] for _ in range(10)]
    for i in range(10):
        g[i] = list(map(int, input().split()))

    from collections import defaultdict
    c_lis = defaultdict(int)
    for i in range(h):
        for j in input().split():
            tmp = int(j)
            if abs(tmp) != 1:
                c_lis[tmp] += 1
    
    dist = dijkstra(1)
    ans = 0
    for key in c_lis:
        ans += c_lis[key]*dist[key]
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

h,w=map(int,input().split())
costs=[]
for _ in range(10):
  costs.append(list(map(int,input().split())))
dd=defaultdict(lambda:0)
for i in map(int,sys.stdin.read().split()):
  dd[i]+=1
  
min_costs=[0]*10
for y in range(10):
  min_costs[y]=costs[y][1]

for _ in range(100):
  for x in range(10):
    for y in range(10):
      min_costs[y]=min(min_costs[y], min_costs[x]+costs[y][x])

ans=0
for i in range(10):
  ans+=dd[i]*min_costs[i]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

h,w=map(int,input().split())
costs=[]
for _ in range(10):
  costs.append(list(map(int,input().split())))
dd=defaultdict(lambda:0)
for i in map(int,sys.stdin.read().split()):
  dd[i]+=1
  
min_costs=[float("inf")]*10
for y in range(10):
  min_costs[y]=costs[y][1]

for _ in range(100):
  for x in range(10):
    if x==1:
      continue
    for y in range(10):
      min_costs[y]=min(min_costs[y], min_costs[x]+costs[y][x])

ans=0
for i in range(10):
  ans+=dd[i]*min_costs[i]
print(ans)

Submission status: Accepted

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

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * n # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

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

e = [[] for _ in range(n)]

for i in range(n):
    for j in range(n):
        e[i].append((c[i][j], j))
        
mp = float('inf')
mplist = [mp]*n
for i in range(n):
    dist = dijkstra(i)
    mplist[i] = dist[1]

chgmp =0
for ih in range(H):
    for iw in range(W):
        if A[ih][iw]!=-1:
            chgmp += mplist[A[ih][iw]]
print(chgmp)

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:
def warshall_floyd(d):
    # d[i][j]: The shortest distance from i to j
    n = len(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 _ in range(10)]
a = [[] for _ in range(h)]

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

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

warshall_floyd(c)

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


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

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
inf=100000
h,w=map(int,input().split())
cost=[]
for i in range(10):
    lst=list(map(int,input().split()))
    cost.append(lst)

def dijkstra(start):
    min_cost=[inf]*10
    min_cost[start]=0
    q=[]
    heappush(q,(0,start))
    while q:
        c,v=heappop(q)
        if v==1:
            return c
        if c>min_cost[v]:
            continue
        for i,nc in enumerate(cost[v]):
            if c+nc<min_cost[i]:
                min_cost[i]=c+nc
                heappush(q,(c+nc,i))

to_one=[None]*10
for i in range(10):
    to_one[i]=dijkstra(i)
ans=0
for i in range(h):
    lst=list(map(int,input().split()))
    for j in lst:
        if j!=-1:
            ans+=to_one[j]
print(ans)

Submission status: Accepted

Solution code:
import heapq
h, w = map(int, input().split())
cs = [[] for _ in range(10)]
g = [[] for _ in range(10)]
for i in range(10):
    lis = list(map(int, input().split()))
    for j in range(10):
        if i == j:
            continue
        g[j].append((i,lis[j]))
ds = [-1]*10
hq = [(0,1)]
while hq:
    c,idx = heapq.heappop(hq)
    if ds[idx] != -1:
        continue
    ds[idx] = c
    for i in g[idx]:
        if ds[i[0]] == -1:
            heapq.heappush(hq,(c+i[1],i[0]))
res = 0
for i in range(h):
    lis = list(map(int, input().split()))
    for j in lis:
        if j != 1 and j != -1:
            res += ds[j]
print(res)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from scipy.sparse.csgraph import floyd_warshall

h,w=nii()
c=[lnii() for i in range(10)]
a=[lnii() for i in range(h)]

s=floyd_warshall(c)

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

Submission status: Accepted

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

from collections import defaultdict

H, W = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
for w in range(10):
    for u in range(10):
        for v in range(10):
            if c[u][v] > c[u][w] + c[w][v]:
                c[u][v] = c[u][w] + c[w][v]

cost = 0
for _ in range(H):
    lv = map(int, input().split())
    for v in lv:
        if v >= 0:
            cost += c[v][1]
print(cost)

Submission status: Accepted

Solution code:
def warshall_floyd(d):
    for i in range(10):
        for j, c2 in enumerate(d[j][i] for j in range(10)):
            for k, (c1,c3) in enumerate(zip(d[j], d[i])):
                if c1 > c2+c3:
                    d[j][k] = c2+c3
    return d

h,w = map(int,input().split())
d=[list(map(int,input().split())) for _ in range(10)] 
a=[list(map(int,input().split())) for _ in range(h)]
a_cnt=[0]*10
for i in range(h):
    for j in range(w):
        if a[i][j]==-1:
            continue
        a_cnt[a[i][j]]+=1
d=warshall_floyd(d)
ans=0
for i,j in enumerate(a_cnt):
    ans+=d[i][1]*j
print(ans)

Submission status: Accepted

Solution code:
INFTY = 10**4+10
H,W = map(int,input().split())
C = [list(map(int,input().split())) for _ in range(10)]
cost = [[INFTY for _ in range(10)] for _ in range(10)]
for i in range(10):
    for j in range(10):
        cost[i][j] = C[i][j]
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])
A = [list(map(int,input().split())) for _ in range(H)]
tot = 0
for i in range(H):
    for j in range(W):
        if A[i][j]==1 or A[i][j]==-1:continue
        tot += cost[A[i][j]][1]
print(tot)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from heapq import heappop, heappush
H, W = mapint()
Cs = [list(mapint()) for _ in range(10)]
lis = []
for h in range(H):
    lis.extend(list(mapint()))

def dijkstra(start):
    Q = [(0, start)]
    checked = [0]*10
    while Q:
        d, v = heappop(Q)
        checked[v] = 1
        if v==1:
            return d
        for i in range(10):
            if not checked[i]:
                heappush(Q, (d+Cs[v][i], i))

costs = [0]*10
for i in range(10):
    costs[i] = dijkstra(i)

from collections import Counter
c = Counter(lis)
ans = 0
for i in range(10):
    ans += costs[i]*c[i]
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])


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

print(ans)

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

cost = [float("INF")]*(10)
cost[1] = 0
cnt = 0
while cnt < 10:
    cnt += 1
    for i in range(10):
        for j in range(10):
            cost[j] = min(cost[j],cost[i]+C[j][i])

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

Submission status: Accepted

Solution code:
# dijkstraで解く
from heapq import heappush, heappop
from collections import defaultdict
INF = float("inf")

def dijkstra(C, g):
    '''
    各頂点からg「まで」の最小コストを求める
    C ... 隣接行列で表されたコスト
    g ... 終点
    '''
    n = len(C)
    min_cost = [INF] * n
    min_cost[g] = 0
    visited = defaultdict(bool)
    H = [(0, g)]

    while H:
        v_cost, v = heappop(H)
        if visited[v]: continue
        visited[v] = True
        for u in range(n):
            new_cost = C[u][v] + v_cost
            if new_cost < min_cost[u]:
                min_cost[u] = new_cost
                heappush(H, (new_cost, u))

    return min_cost


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

min_cost = dijkstra(C, 1)

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

print(ans)

Submission status: Accepted

Solution code:
def floyd_warshall(dp, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp

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

c = floyd_warshall(c, 10)

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
from collections import defaultdict
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()


def main():
    H, W = map(int, input().split())
    C = [list(map(int, input().split())) for _ in range(10)]
    """
    備忘録としてワ―シャルフロイドによる実装も試してみる。
    wikipediaの解説が意外とわかりやすい？
    """
    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])
    
    d = defaultdict(int)
    for _ in range(H):
        A = list(map(int, input().split()))
        for a in A: d[a] += 1
    ans = 0
    for i in range(10): ans += C[i][1] * d[i]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()


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

    cost = [10**18] * 10
    cost[1] = 0
    q = [(0, 1)]
    while q:
        c, u = heappop(q)
        if c > cost[u]: continue
        for i in range(10):
            if i == u: continue
            if c + C[i][u] < cost[i]:
                cost[i] = cost[u] + C[i][u]
                heappush(q, (cost[i], i))
    
    d = defaultdict(int)
    for _ in range(H):
        A = list(map(int, input().split()))
        for a in A: d[a] += 1
    ans = 0
    for i in range(10): ans += cost[i] * d[i]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
import heapq

sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

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

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

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


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

def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret

def kaijyo_kai(n, k):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * (k+i))% MOD)
    return ret


def dijkstra(graph, start, n):
    h = []
    heapq.heappush(h, (0, start))
    costs = [INF for _ in range(n)]
    while h:
        cost, cur = heapq.heappop(h)
        if costs[cur] != INF:
            continue
        costs[cur] = cost
        for edge in graph[cur]:
            ecost, tgt = edge
            if costs[tgt] == INF:
                heapq.heappush(h, (cost + ecost, tgt))

    return costs

def solve():
    n, m = getList()
    graph = [[] for i in range(10)]
    magic = []
    for i in range(10):
        mg = getList()
        for j, mm in enumerate(mg):
            if i != j:
                graph[i].append((mm, j))

    for i in range(10):
        magic.append(dijkstra(graph, i, 10))
    # print(graph)
    # print(magic)


    ans = 0
    for i in range(n):
        for j in getList():
            if j != -1:
                ans += magic[j][1]

    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()


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

Submission status: Accepted

Solution code:
from types import CodeType
import unittest


def solve():
    return 0


def main():
    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):
                if c[i][k] + c[k][j] < c[i][j]:
                    c[i][j] = c[i][k] + c[k][j]
    total = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] == -1:
                continue
            total += c[a[i][j]][1]
    print(total)


if __name__ == "__main__":
    main()


class Test(unittest.TestCase):
    def test_case1(self):
        expected = 0
        actual = solve()
        self.assertEqual(actual, expected)

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 < 0: continue
        ans += C[a][1]
print(ans)

Submission status: Accepted

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

# solve
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]

from collections import Counter
cnt = Counter()
for __ in range(H):
    # A.append(list(map(int, input().split())))
    cnt.update(list(map(int, input().split())))

ans = 0
for i in cnt.keys():
    if i == -1:
        continue
    ans += C[i][1] * cnt[i]

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()))
C = []
for _ in range(10):
    row = list(map(int, input().split()))
    C.append(row)

number_count = {i: 0 for i in range(10)}
for _ in range(H):
    row = list(map(int, input().split()))
    for num in row:
        if num == -1:
            continue
        number_count[num] += 1

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

# for row in C:
    # print(' '.join(map(str, row)))

# print(number_count)
result = 0
for k, v in number_count.items():
    result += C[k][1] * v

print(result)

Submission status: Accepted

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

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

    mn_c=[c[s][1] for s in range(10)]
    return mn_c

mn_c=warshall_floyd(c)

sm=0
for i in range(h):
    a=list(map(int,input().split()))
    for k in a:
        if k>=0:
            sm+=mn_c[k]

print(sm)

Submission status: Accepted

Solution code:
from itertools import permutations


def warshallfloyd(N, DIST):  # ワーシャルフロイド法:全頂点対最短経路 O(n**3)
    # DIST:隣接行列
    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])
    return DIST


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, dist = 0, warshallfloyd(10, c)
for ai in a:
    for aij in ai:
        if aij != -1:
            ans += dist[aij][1]
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush

def dijkstra(G, start):
    n = len(G)
    dist = [float("inf")]*n
    visited = set()
    heap = []
    heap.append((0, start))

    while heap and len(visited) != n:
        d, cur = heappop(heap)
        if cur in visited:
            continue
        visited.add(cur)
        dist[cur] = d
        for to in range(10):
            if to not in visited:
                heappush(heap, (d+G[cur][to], to))
    return dist

h,w = map(int, input().split())
c = [list(map(int, input().split())) for i in range(10)]
rc = [[0]*10 for i in range(10)]
for i in range(10):
    for j in range(10):
        rc[i][j] = c[j][i]
a = [list(map(int, input().split())) for i in range(h)]
dist = dijkstra(rc, 1)
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] != -1:
            ans += dist[a[i][j]]
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
解説PDFを読んで書き直した。
ワーシャル-フロイド法を用いる。
"""

def warshall_floyd(c_lsit_list):
    for i in range(10):
        for j in range(10):
            for k in range(10):
                c_lsit_list[j][k] = min(
                    c_lsit_list[j][i] + c_lsit_list[i][k],
                    c_lsit_list[j][k]
                )
    min_c_list = [c_lsit_list[i][1] for i in range(10)]
    return min_c_list

def main():
    H, W = map(int, input().split())
    c_lsit_list = [list(map(int, input().split())) for i in range(10)]
    A_lsit_list = [list(map(int, input().split())) for i in range(H)]

    A_bucket = [0]*10
    for A_list in A_lsit_list:
        for A in A_list:
            if A >= 0:
                A_bucket[A] += 1

    min_c_list = warshall_floyd(c_lsit_list)

    print(sum([A_bucket[i]*min_c_list[i] for i in range(10)]))
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

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


def bellman_ford(s):
	d = [float('inf')]*10 # 各頂点への最小コスト
	d[s] = 0 # 自身への距離は0
	for i in range(10):
		update = False # 更新が行われたか
		for x, y, z in g:
			if d[y] > d[x] + z:
				d[y] = d[x] + z
				update = True
		if not update:
 			break
		# 負閉路が存在
		if i == 9:
			return -1
	return d

g = []
for i in range(10):
	for j in range(10):
		x,y,z = j,i,c[i][j]
		g.append([x,y,z])

MINCOST = bellman_ford(1)

sum = 0
for j in range(h):
	for i in range(0,10):
		sum += MINCOST[i]*collections.Counter(a[j])[i]
print(sum)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
C = []
wall = []

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

for _ in range(H):
  wall += 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])

ans = 0
for x in wall:
  if x == -1:
    continue
  else:
    ans += C[x][1]

print(ans)

Submission status: Accepted

Solution code:
import heapq

H, W = map(int, input().split())
graph = []
wall = []

for _ in range(10):
  graph.append(list(map(int, input().split())))

for _ in range(H):
  wall += list(map(int, input().split()))

def dijkstra(s):
  INF = 10**5
  hq = [(0, s)]
  heapq.heapify(hq)
  cost = [INF] * 10
  cost[s] = 0
  while hq:
    c, v = heapq.heappop(hq)
    if c > cost[v]:
      continue
    for u, d in enumerate(graph[v]):
      tmp = d + cost[v]
      if tmp < cost[u]:
        cost[u] = tmp
        heapq.heappush(hq, (tmp, u))
  return cost[1]

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

ans = 0
for x in wall:
  if x == -1 or x == 1:
    continue
  else:
    ans += mincost[x]

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
dist = [list(map(int, input().split())) for _ in range(10)]
for i in range(10):
    for j in range(10):
        for k in range(10):
            dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])
ans = 0
for _ in range(H):
    for i in list(map(int, input().split())):
        if i == 1 or i == -1:
            continue
        ans += dist[i][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)]
dp = [float("INF")]*(10)
dp[1] = 0
cnt = 0
while cnt <= 10:
    cnt += 1
    for i in range(10):
        for j in range(10):
            dp[j] = min(dp[j],dp[i]+C[j][i])

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

Submission status: Accepted

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

h, w = map(int, input().split())
ma = [ list(map(int,input().split(" "))) for i in range(10)]
sco = [ list(map(int,input().split(" "))) for i in range(h)]
a = csr_matrix(ma)
b = dijkstra(a)
ans = 0
for i in range(h):
  for j in range(w):
    num = sco[i][j]
    if num != -1:
      ans += b[num][1]
print(int(ans))

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

h,w = mi()
c = [[float('inf') for j in range(10)]for i in range(10)]

for i in range(10):
    cc = li()
    for j in range(10):
        c[i][j] = cc[j]

# cost of i to j

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):
    w = li()
    for j in w:
        if j == -1:
            continue
        ans += c[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)]

dp = [float("INF")]*(10)
dp[1] = 0
cnt = 0
while cnt <= 10:
    cnt += 1
    for i in range(10):
        for j in range(10):
            dp[j] = min(dp[j],dp[i]+C[j][i])

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