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:
h,w = map(int, input().split())
c = []
a = []
for i in range(10):
  c.append(list(map(int, input().split())))
for i in range(h):
  a.append(list(map(int, input().split())))
 
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 = map(int, input().split(' '))
tbl = [list(map(int, input().split(' '))) for i in range(10)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            tbl[i][j] = min(tbl[i][j], tbl[i][k]+tbl[k][j])
wall = [list(map(int, input().split(' '))) for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        num = wall[i][j]
        if num == -1:
            continue
        else:
            ans += tbl[num][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 h in range(H)]

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

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 h in range(H):
  for w in range(W):
    if A[h][w] >= 0:
      ans += c[A[h][w]][1]
print(ans)

Submission status: Accepted

Solution code:
'''
　 ∧_,,∧    究極奥義「WAがACになーれ！！」
　（`・ω・)つ━☆・*。
　⊂　　 ノ 　　　・゜+.
　 し’´Ｊ　　*・ 
'''
import sys
input = sys.stdin.readline
h,w=map(int,input().split())
d=[list(map(int,input().split())) for i in range(10)]
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])
a=[list(map(int,input().split())) for i in range(h)]
# for i in range(10):
#     print(d[i])
ans=0
for i in range(h):
    for j in range(w):
        if a[i][j]!=-1:
            ans+=d[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) ] 

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
B=warshall_floyd(C)
  
ans=0
for i in range(H):
  for j in range(W):
    if A[i][j]!=-1:
      ans+=B[ A[i][j] ][1]
print(ans)

Submission status: Accepted

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

H, W = map(int, input().split())
path = shortest_path(np.array(tuple(tuple(map(int, input().split())) for _ in range(10))))
A = np.array(tuple(tuple(map(int, input().split())) for _ in range(H))).flatten()

print(int(sum(path[n][1] for n in A if n not in [-1, 1])))

Submission status: Accepted

Solution code:

def warshal_floyd(weights,N):
    d=weights
    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])
    return d

if __name__ == '__main__':
    H,W=list(map(int,input().split()))
    weights=[[None for i in range(10)] for j in range(10)]
    for i in range(10):
        Cs = list(map(int, input().split()))
        for j in range(10):
            weights[i][j]=Cs[j]
    wall=[]

    for i in range(H):
        temp=list(map(int,input().split()))
        wall.append(temp)

    paths=warshal_floyd(weights,10)
    cost=0

    for row in wall:
        for a in row:
            if a==-1:
                continue
            else:
                cost+=paths[a][1]
    print(cost)

Submission status: Accepted

Solution code:
def dijkstra(v, G):
    import heapq

    ret = [10 ** 10] * len(G)
    ret[v] = 0
    q = [(ret[i], i) for i in range(len(G))]
    heapq.heapify(q)

    while len(q):
        tmpr, u = heapq.heappop(q)
        if tmpr == ret[u]:
            for w, l in G[u]:
                if ret[w] > ret[u] + l:
                    ret[w] = ret[u] + l
                    heapq.heappush(q, (ret[w], w))
    return ret


H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(10)]
G = [[] for _ in range(10)]
for i in range(10):
    for j in range(10):
        if i != j:
            G[i].append((j, C[i][j]))

LUT = [dijkstra(i, G)[1] for i in range(10)]

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

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 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 = map(int, input().split())

edges = [[] for i in range(10)]

for _from in range(10):
    line = list(map(int, input().split()))
    for to in range(10):
        if _from == to:
            continue
        cost = line[to]
        edges[_from].append([to, cost])

cost_to_1 = [10**5] * 10
cost_to_1[1] = 0

for num in range(10):
    if num == 1:
        continue
    min_cost_to = [10**5] * 10
    min_cost_to[num] = 0
    todo = []
    for to, cost in edges[num]:
        if to == num:
            continue
        min_cost_to[to] = cost
        todo.append(to)

    while todo:
        now = todo.pop()
        cost = min_cost_to[now]
        for to, add_cost in edges[now]:
            if to == now:
                continue
            if cost + add_cost < min_cost_to[to]:
                min_cost_to[to] = cost + add_cost
                todo.append(to)
            else:
                continue

    cost_to_1[num] = min_cost_to[1]

ans = 0
for i in range(h):
    line = list(map(int, input().split()))
    for num in line:
        if num == -1 or num == 1:
            continue
        ans += cost_to_1[num]

print(ans)

Submission status: Accepted

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

for i in range(10):
    dist[i]=A[i][1]

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

s=0
for i in range (H):
    T=list(map(int,input().split()))
    for j in range(W):
        if T[j]==-1:
            continue
        else:
            s+=dist[T[j]]
print(s)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
ans = 0
c = [list(map(int,input().split()))for i in range(10)]
a = [list(map(int,input().split()))for _ in range(h)]
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])
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:
a,b = list(map(int,input().split()))
mat = []
for i in range(10):
  mat.append(list(map(int,input().split())))

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

import heapq  
d_ans = [0]*10

for i in range(10):
  d = [3000 *20] * 10
  d[i] = 0
  h = []
  heapq.heappush(h,(d[i],i))
  #print(h)
  while not len(h) == 0:
    (di, v) = heapq.heappop(h)
    if v == 1:
      break
    for j in range(10):
      #print(i,j,di,v)
      if d[j] > d[v] + mat[v][j]:
        d[j] = d[v] + mat[v][j]
        heapq.heappush(h,(d[j],j))
  #print(d)
  d_ans[i] = d[1]

ans = 0
for x in xs:
  if x != -1:
    ans += d_ans[x]
print(ans)

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    inf = 10 ** 13
    h, w = list(map(int, input().rstrip('\n').split()))
    wn = 10
    wl = [[inf] * wn for _ in range(wn)]

    for i in range(wn):
        twl = list(map(int, input().rstrip('\n').split()))
        for j in range(wn):
            wl[i][j] = twl[j]

    for i in range(wn):
        for j in range(wn):
            for k in range(wn):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])

    cost = 0
    for i in range(h):
        hw = list(map(int, input().rstrip('\n').split()))
        for j in range(w):
            if hw[j] != -1:
                cost += wl[hw[j]][1]
    print(cost)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
C = [list(map(int,input().split())) for _ in range(10)]
# warshall-floydで各数字から1に変換するまでの最小魔力を計算
for k in range(10):
    for j in range(10):
        for i in range(10):
            C[i][j] = min(C[i][j], C[i][k]+C[k][j])
# print(C)
powerto1 = {idx: C[idx][1] for idx in range(10)}
#print(powerto1)
ans = 0
for _ in range(H):
    A = list(map(int,input().split()))
    for i in range(W):
        if A[i] != -1:
            ans += powerto1[A[i]]
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
C = [list(map(int,input().split())) for _ in range(10)]
# warshall-floydで各数字から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])
# print(C)
powerto1 = {idx: C[idx][1] for idx in range(10)}
#print(powerto1)
ans = 0
for _ in range(H):
    A = list(map(int,input().split()))
    for i in range(W):
        if A[i] != -1:
            ans += powerto1[A[i]]
print(ans)

Submission status: Accepted

Solution code:
dp=[[0 for j in range(10)] for i in range(10)]
import numpy as np

h,w=map(int,input().split())
dp=np.array(dp)
for i in range(10):
    s=list(map(int,input().split()))
    for j in range(10):
        dp[i][j]=s[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(h):
    s=list(map(int,input().split()))
    for j in range(w):
        if s[j]!=-1 and s[j]!=1:
            c+=dp[s[j]][1]
print(c)

Submission status: Accepted

Solution code:
dp=[[0 for j in range(10)] for i in range(10)]

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

Submission status: Accepted

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

manacost = [0]*11
for i in range(10):
    if i == 1:
        continue
    manacost[i] = c[i][1]
    stack = []
    for j, m in enumerate(c[i]):
        if j == 1 or i == j:
            continue
        else:
            if manacost[i] > m:
                stack.append((j, m, 0))
    while len(stack):
        j, m, t = stack.pop()
        for k, n in enumerate(c[j]):
            if j == k:
                continue
            elif k == 1:
                manacost[i] = min(manacost[i], m+n)
            else:
                if manacost[i] > m+n and t < 9:
                    stack.append((k, n+m, t+1))
for ary in A:
    for a in ary:
        ans += manacost[a]
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)]


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


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

Submission status: Accepted

Solution code:
# atcoder : python3 (3.4.3)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
mod = 10**9+7

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

from scipy.sparse.csgraph import floyd_warshall
D = floyd_warshall(C)

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

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

print(int(ans))

Submission status: Accepted

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

H, W = [int(x) for x in input().strip().split()]
C = [0 for _ in range(10)]
for i in range(10):
    C[i] = [int(x) for x in input().strip().split()]

isChanged = True
while isChanged:
    isChanged = False
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if C[i][j] > C[i][k] + C[k][j]:
                    C[i][j] = C[i][k] + C[k][j]
                    isChanged = True
    if not isChanged:
        break

ans = 0
for h in range(H):
    W = [int(x) for x in input().strip().split()]
    for w in W:
        if w == -1:
            continue
        ans += C[w][1]

print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
from collections import Counter
h, w = [int(i) for i in sys.stdin.readline().split()]
c_ls = []
A = dict()
for i in range(10):
    c_ls.append([int(i) for i in sys.stdin.readline().split()])
c_ls_true = {i : [0 for j in range(10)] for i in range(10)}
for i in range(10):
    for j in range(10):
        c_ls_true[i][j] = c_ls[j][i]

shortest_path = {-1 : 0}
que = [(0, 1)]
already = set()
while len(que) > 0:
    cur_cost, cur = heapq.heappop(que)
    if cur in already:
        continue
    already.add(cur)
    shortest_path[cur] = cur_cost
    for _next, cost in enumerate(c_ls_true[cur]):
        if _next not in already:
            heapq.heappush(que, (cur_cost + cost, _next))
    if len(already) == 10:
        break
ct = Counter()
for i in range(h):
    inp = [int(i) for i in sys.stdin.readline().split()]
    A[i] = inp
    ct.update(inp)
res = 0
for k, v in ct.items():
    res += shortest_path[k] * v
print(res)

Submission status: Accepted

Solution code:
from itertools import permutations as per
h,w = map(int,input().split())
c = [list(map(int,input().split())) for i in range(10)]
ans = 0
mc = [0]*10
for i in range(10):
  mc[i] = c[i][1]
for i in range(1,10):
  for j in per([0,2,3,4,5,6,7,8,9],i):
    cur = 0
    for k in range(1,i):
      cur += c[j[k-1]][j[k]]
    cur += c[j[i-1]][1]
    mc[j[0]] = min(mc[j[0]],cur)
for i in range(h):
  a = list(map(int,input().split()))
  for j in a:
    if j != -1:
      ans += mc[j]
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
h, w = map(int, input().split())
c = [ list(map(int, input().split())) for _ in range(10) ]
csr = csr_matrix(c)
A = dijkstra(csr)
Q = [0]*10
for i in range(10):
  Q[i] = int(A[i][1])
ans = 0
for _ in range(h):
  for i in map(int, input().split()):
    if not i==-1:
      ans += Q[i]
print(ans)

Submission status: Accepted

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

from collections import defaultdict
cost = [[float("inf") for i in range(10)] for j in range(10)]
for i in range(10):
    cl = list(map(int,input().split()))
    for j in range(10):
        cost[i][j] = cl[j]

# cost[i][j]: 頂点v_iから頂点v_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])

ans = 0
for _ in range(h):
    al = list(map(int,input().split()))
    for a in al:
        if a == -1:
            continue
        ans += cost[a][1]

print(ans)

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, input().split())
    C = list(list(map(int, input().split())) for _ in range(10))
    A = list(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)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

ans = 0
for _ in range(H):
    for a in map(int, input().split()):
        if a!=-1:
            ans += P[a][1]
    
print(ans)

Submission status: Accepted

Solution code:
# D - Wall

from scipy.sparse.csgraph import floyd_warshall

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

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
X = [[int(a) for a in input().split()] for _ in range(10)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            X[i][j] = min(X[i][j], X[i][k] + X[k][j])
print(sum([sum([0 if a == "-1" else X[int(a)][1] for a in input().split()]) for _ in range(H)]))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
c = [LIST() for _ in range(10)]
A = [LIST() for _ in range(H)]

dist = [[INF]*10 for _ in range(10)]
for i in range(10):
    for j in range(10):
        dist[i][j] = c[i][j]

graph = csr_matrix(dist)
dist_mat = floyd_warshall(graph, directed=True)

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(10)]
o=[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 l[i][j]>l[i][k]+l[k][j]:
        l[i][j]=l[i][k]+l[k][j]

v=[[l[j][1] if j>=0 else 0 for j in i] for i in o]
print(sum(map(sum,v)))

Submission status: Accepted

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

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

ans = 0
warshallFloyd(dp)
for i in range(H):
    for j in range(W):
        a = A[i][j]
        if a == -1:
            continue
        else:
            ans += dp[a][1]
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
l=[] # l[i][j]は有向グラフ上での辺i->jの長さ
for i in range(10):
    l.append(list(map(int,input().split())))

# この有向グラフを1から逆方向に辿っていくことを考える。
dis=[l[i][1] for i in range(10)] # 頂点1からiまでの距離
# print(dis)
for i in range(9):
    dis=[min(dis[v],min([dis[u]+l[v][u] for u in range(10)])) for v in range(10)]
    # print(dis)

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

ans=sum([A.count(i)*dis[i] for i in range(10)])
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
l=[]
for i in range(10):
  l.append(list(map(int,input().split())))
way=[]
for i in range(h):
  way.append(list(map(int,input().split())))
from collections import deque
q=deque([[0,0]])
for k in range(10):
  for j in range(10):
    for i in range(10):
      l[i][j]=min(l[i][j],l[i][k]+l[k][j])
cost=0
d=[[-1 for i in range(w)] for j in range(h)]
if way[0][0]!=-1:
  cost+=l[way[0][0]][1]
d[0][0]=1
move=[[0,1],[0,-1],[-1,0],[1,0]]
while q:
  m=q.popleft()
  for i in move:
    x=m[0]+i[0]
    y=m[1]+i[1]
    if x<0 or y<0 or x>=h or y>=w:
      pass
    elif d[x][y]==1:
      pass
    else:
      d[x][y]=1
      if way[x][y]!=-1:
        cost+=l[way[x][y]][1]
      way[x][y]=1
      q.append([x,y])
print(cost)

Submission status: Accepted

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

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

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

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

#print(warshall_floyd(d))

cost = warshall_floyd(d)

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

print(ans)

Submission status: Accepted

Solution code:
H,W = (int(i) for i in input().split())

C = []
#C[i][j]
for i in range(10):
  C.append([int(j) for j in input().split()])

for s in range(10):
  for i in range(10):
    for j in range(10):
      new_costs = []
      for k in range(10):
        new_costs.append(C[i][k] + C[k][j])

      C[i][j] = min(min(new_costs),C[i][j])

A_dict = {}
for i in range(H):
  A = [int(i) for i in input().split()]
  for a in A:
    A_dict[a] = A_dict.get(a,0)+1

ans = 0
for A in A_dict.keys():
  if A != -1 and A != 1:
    ans += C[A][1]*A_dict[A]

print(ans)

Submission status: Accepted

Solution code:
# ABC079d
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = 10
d = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(n):
    d[i][i] = 0  # 自身のところに行くコストは０


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


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

a = [list(map(int, input().split())) for _ in range(h)]
cou = [0]*10
for i in a:
    for j in range(10):
        cou[j] += i.count(j)
ans = 0
for i in range(10):
    ans += cou[i]*d[i][1]
# for i in range(10):
    # print(d[i][1])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W = MI()
    N=10
    def warshall_floyd(d, N):
        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])

    d=[[float("inf")] * N for i in range(N)]
    for i in range(N):
        d[i][i] = 0
    
    #-------辺入力------
    for i in range(N):
        C = LI()
        for j in range(N):
            d[i][j] = min(d[i][j], C[j])
    warshall_floyd(d, N)

    to = 1
    ans = 0
    for i in range(H):
        wall = LI()
        for j in range(W):
            num = wall[j]
            if num==-1:
                continue
            # print(num,d[num][to])
            ans += d[num][to]
    # print(*d,sep="\n")
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    H, W = map(int, sys.stdin.readline().split())
    ca = np.array(sys.stdin.read().split(), dtype=np.int64)
    cost = ca[:100].reshape(10, 10)
    A = ca[100:]
    
    min_cost = floyd_warshall(csgraph=csr_matrix(cost), directed=True)

    total_cost = min_cost[np.absolute(A)].T[1].astype(np.int64).sum()
    print(total_cost)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    H, W = map(int, sys.stdin.readline().split())
    cost = np.array([sys.stdin.readline().split() for _ in range(10)], dtype=np.int64)
    A = np.array(sys.stdin.read().split(), dtype=np.int64)
    
    graph = csr_matrix(cost)
    dist = floyd_warshall(csgraph=graph, directed=True)

    ans = dist[np.absolute(A)].T[1].astype(np.int64).sum()
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    h, w = map(int, input().split())
    cc = [list(map(int, input().split())) for _ in range(10)]
    # 数字ごとにカウント
    cnt = [0] * 10
    for _ in range(h):
        for a in map(int, input().split()):
            if a == -1: continue
            cnt[a] += 1
    # print(cnt)

    # ダイクストラで各数から1までの最小コストを求める
    cto1 = [-1] * 10
    hp = []
    heappush(hp, [0, 1])
    while hp:
        cost, u = heappop(hp)
        if cto1[u] != -1: continue
        cto1[u] = cost
        for v in range(10):
            if cto1[v] != -1: continue
            heappush(hp, [cost + cc[v][u], v])
    # print(cto1)

    # 個数とコストの積を合計して答え
    ans = sum(an * ac for an, ac in zip(cnt, cto1))
    print(ans)

main()