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

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

f=True

while f:
    f=False
    for i in range(10):
        for j in range(10):
            temp=[]
            for k in range(10):
                if co[i][k]<co[i][j] and co[k][j]<co[i][j]:
                    temp.append(co[i][k]+co[k][j])
            if len(temp) >= 1:
                if co[i][j] > min(temp):
                    co[i][j] = min(temp)
                    f = True




for i in range(10):
    c[i]=co[i][1]


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

Submission status: Accepted

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

# ベルマンフォード法
#c=[[random.randint(1, 10) for i in range(n)] for i in range(n)]
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 or a[i][j]==1:
            continue
        else:
            ans+=c[a[i][j]][1]
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(200000)

N, M = map(int, input().split())

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

paint=set([])
dicts={ i:0 for i in range(10)}
for i in range(N):
    input_temp = list(map(int, input().split()))
    temp=[]
    
    for j in input_temp:
        if j != -1:
            dicts[j] += 1
            temp.append(j)
    paint = paint | set(temp)


search_index = set([0,1,2,3,4,5,6,7,8,9])
def dfs(now_index, direct_distance, now_value, before_index, goal_index):
    
    if direct_distance < now_value:
        return direct_distance
    if now_index == goal_index:
        return now_value
    
    mins=[]
    temp_search_index = search_index - set([now_index, before_index])
    for i in temp_search_index:
        mins.append(dfs(i, 
                        direct_distance, 
                        now_value+convert[now_index][i], 
                        now_index, 
                        goal_index)
                   )
    return min(mins)

sums=0
for start in paint:
    if start != 1:
        sums += dicts[start] * dfs(start, convert[start][1], 0, -1, 1)

print(sums)

Submission status: Accepted

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

dp = [[c[i][j] for j in range(10)] for i in range(10)]


for i in range(10):
    for j in range(10):
        for k in range(10):

            dp[j][k] = min(dp[j][i]+dp[i][k], dp[j][k])

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

cost=[C[i][1] for i in range(10)]+[0]
cnt=0
for i in range(h):
    for j in range(w):
        cnt +=cost[A[i][j]]
print(cnt)

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 j 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])
cost=[C[i][1] for i in range(10)]
cnt=0
for i in range(h):
    for j in range(w):
        add=A[i][j]
        if add!=-1:
            cnt +=cost[add]
print(cnt)

Submission status: Accepted

Solution code:
import copy
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)]
# cost = [[-1]*10 for i in range(10)]
# for j in range(10):
#     cost[j] = [[c[i][j], i] for i in range(10)]
cost = [-1]*10
cost[1] = 0

dp = [[-1]*10 for i in range(10)]
for i in range(10):
    dp[i][i] = 0


def search_cost(i, j, reached):
    # if dp[i][j] != -1:
    #     return dp[i][j]
    if cost[i] != -1:
        return cost[i]
    tmp_list = copy.copy(reached)
    tmp_list.append(i)
    ret = c[i][j]

    for k in range(10):
        if k == i or k == 1 or k in reached:
            continue
        else:
            tmp = c[i][k] + search_cost(k, j, tmp_list)
            ret = min(tmp, ret)
            if ret <= 2:
                break
            #print("i:"+str(i) + "k:" + str(k) + "j:"+str(j) + "=" + str(tmp))

    # dp[i][j] = ret
    # for i in range(10):
    #     print(dp[i])
    return ret


for i in range(10):
    if i == 1:
        continue
    else:
        if c[i][1] <= 2:
            dp[i][1] = c[i][1]
            cost[i] = c[i][1]
        else:
            cost[i] = search_cost(i, 1, [])
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:
# D
from collections import Counter
from collections import deque
h, w = map(int, input().split())

cost = [[] for _ in range(10)]
for i in range(10):
    row = map(int, input().split())
    for ind, v in enumerate(row):
        if ind == i:
            cost[i].append(float('inf'))
        else:
            cost[i].append(v)

nums = []
for _ in range(h):
    arow = list(map(int, input().split()))
    nums += arow
counter = Counter(nums)

### dijkstra
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

total = 0
for num, cnt in counter.items():
    if (num == -1) or (num == 1):
        continue
    else:
        dist = dijkstra(s=num, n=10, w=10*10, cost=cost)
        total += dist[1]*cnt
print(total)

Submission status: Accepted

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

def WarshallFloyd(V: int, cost: "List[List[int]]"):
    """
    全ての頂点対の間の最短距離を求めます。
    ==============
    V: 頂点数
    cost: 隣接行列(辺が存在しない部分はINF)
    --------------
    cost: 最短距離の行列
    """
    INF = 1e18
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if cost[i][k] != INF and cost[k][j] != INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    return cost

def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):
    cost = WarshallFloyd(len(c), c)
    C = [0] * 10
    for a in A:
        for aa in a:
            if aa != -1:
                C[aa] += 1
    c = 0
    for i in range(10):
        c += cost[i][1] * C[i]
    print(c)
    return


# Generated by 1.1.5 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:
def resolve():
    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])
    costs = [c[i][1] for i in range(10)]
    costs += [0]  # -1の分
    ans = 0
    for i in range(h):
        for j in range(w):
            ans += costs[a[i][j]]
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from sys import stdin
H, W = [int(_) for _ in stdin.readline().rstrip().split()]
C = [list(map(int, stdin.readline().rstrip().split())) for _ in range(10)]
A = [list(map(int, stdin.readline().rstrip().split())) for _ in range(H)]
D = [0]*10

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

warshall_floyd()
for i in range(10):
    D[i] = C[i][1]
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] >= 0:
            ans += D[A[i][j]]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

a2 = [_ for _ in a if _ not in [-1, 1]]

c_min = [c_tmp[1] for c_tmp in c]

while True:
    c_tmp = [_ for _ in c_min]
    for i in [0, 2, 3, 4, 5, 6, 7, 8, 9]:
        for j in [0, 2, 3, 4, 5, 6, 7, 8, 9]:
            if i == j:
                continue
            if c_min[i] >= c[i][j] + c_tmp[j]:
                c_min[i] = c[i][j] + c_tmp[j]

    if c_tmp == c_min:
        break

res = 0
for ai in a2:
    res += c_min[ai]
print(res)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra,floyd_warshall
H, W = map(int, input().split())

A = []
for _ in range(10):
  A.append(list(map(int, input().split())))
A = np.array(A)
c = []
for _ in range(H):
  c.append(list(map(int, input().split())))
c = np.array(c)
A = floyd_warshall(A)
C = A[0:,1]

ans = 0
for i in c:
  for j in i:
    if j != -1:
      ans += C[j]
print (int(ans))

Submission status: Accepted

Solution code:
import heapq

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

distance = [10**6 for i in range(10)]
visited = [False for i in range(10)]
heap = []
cost = 0

distance[1] = 0
visited[1] = True
for i in range(10):
    heapq.heappush(heap,[C[i][1],i])

while heap:
    minedge = heapq.heappop(heap)
    if visited[minedge[1]]:
        continue
    v = minedge[1]
    distance[v] = minedge[0]
    visited[v] = True
    for i in range(10):
        if not visited[i]:
            heapq.heappush(heap,[C[i][v]+distance[v],i])

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

print(cost)

Submission status: Accepted

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

    dp = c.copy()

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

    magic = 0
    for row in a:
        for num in row:
            if num == -1:
                continue
            magic += dp[num][1]

    print(magic)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

#最短距離 (V:頂点数,E:辺数)
#BFS : コスト1 O(E)
#Dijkstra : コスト任意 O(ElogE)
#Floyd Warshall O(V^3) →　今回 V=10 → OK

#「「「Floyd Warshall」」」
#→全点間の重み付きグラフ　経路最小化
#点j→点kに行くまでの最小コスト経路(j→k or j→i→k)
#===========================================================
#iを動かして
#「j→i」のコスト　と　「j→i→kのコスト」　の小さいほうを d[j][k]に採用
#ということを繰り返す
#→直感的には、これでは「2点間コスト」or「3点間コスト」の小さいほうを選んでいるだけっぽいで、
#4点間コスト,5点間コスト,...が最小の場合を考慮していないのでは...
#→実は大丈夫
#===========================================================
#・上の例で,右の経由コストがd[j][k]のコストに採用された場合は(i=i0として)
#「j→i0→k」のコスト と　「j→i0→i1→kのコスト」　の小さいほうを d[j][k]に採用
#これをiを動かして繰り返してコストの最小値を求めるのでn点間最小値も網羅している！！

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

Submission status: Accepted

Solution code:
import itertools
import sys
input = sys.stdin.readline
def inputs():
    return [int(x) for x in input().split()]
H,W = inputs()
c = [inputs() for _ in range(10)]
HW = [inputs() for _ in range(H)]
A = (0,9,8,7,6,5,4,3,2)
B = list(itertools.permutations(A))
N = [c[i][1] for i in range(10)]
for i in B:
    a = i[0]
    ans = 0
    for j in range(1,9):
        ans +=c[i[j-1]][i[j]]
        if N[a]<=ans:
          break
        N[a] = min(ans+c[i[j]][1],N[a])    
ans = 0
for i in range(H):
    for j in range(W):
        if HW[i][j]!=-1:
            ans += N[HW[i][j]]
print(ans)

Submission status: Accepted

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

INF = 100000000
def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):

    V = 10
    # WF
    # c = [[INF] * (V) for i in range(V)]
    for k in range(V):
        for i in range(V):
            if c[i][k] == INF : continue
            for j in range(V):
                if c[k][j] == INF: continue
                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)
    return


# Generated by 1.1.4 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 l in range(10)]
a = []
res = 0
for _ in range(h):
    a.extend(list(map(int,input().split())))

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

for sa in a:
    if sa != -1:
        res += c[sa][1]

print(res)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

H, W = map(int, input().split())
C = []
for i in range(9+1):
    c = list(map(int, input().split()))
    C.append(c)

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

def warshall(org, V):
    d = org[:]

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

    return d

V = 10
cost = warshall(C, V)
#print(cost)

ans = 0
for h in range(H):
    for w in range(W):
        if 0 <= A[h][w]:
            ans += cost[A[h][w]][1]

print(ans)

Submission status: Accepted

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

for j in range(h):
    add1=list(map(int,input().split()))
    datalist.extend(add1)
 
storelist=[[[[] for i in range(10)] for i in range(10)] for i in range(10)]
    #わーシャルフロイド法
for i in range(10):
    for j in range(10):
            a=min(magialist[i][j],magialist[i][0]+magialist[0][j])
            storelist[0][i][j]=a
k=1
while k<=9:
    for i in range(10):
        for j in range(10):
                a=min(storelist[k-1][i][j],storelist[k-1][i][k]+storelist[k-1][k][j])
                storelist[k][i][j]=a
    k+=1

uselist=[]
                                                                                        
for j in range(10):
    uselist.append(storelist[9][j][1])
ans=0
for nums in range(h*w):
        if datalist[nums]==-1:
            continue
        else:
            for j in range(10):
                if datalist[nums]==j:
                    ans+=uselist[j]
print(ans)

Submission status: Accepted

Solution code:
#%%
import copy 

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

d = copy.deepcopy(c)

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


ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == 0 or A[i][j] >= 2:
            ans += d[A[i][j]][1]


print(ans)

Submission status: Accepted

Solution code:
def main():
    H, W = (int(i) for i in input().split())
    C = [[int(i) for i in input().split()] for j in range(10)]
    A = [[abs(int(i)) for i in input().split()] for j in range(H)]
    determined = set()
    from collections import deque
    notdetermined = deque()
    r = [0] * 10
    for k in range(10):
        r[k] = C[k][1]
    
    from itertools import permutations
    for sel in range(1,10):
        for p in permutations([0,2,3,4,5,6,7,8,9,],sel):
            cur = 0
            k = p[0]
            for i in p[1:]:
                cur += C[k][i]
                k = i
            else:
                cur += C[k][1]
            if cur < r[p[0]]:
                r[p[0]] = cur
    ans = 0
    for row in A:
        for a in row:
            ans += r[a]
    print(ans)

if __name__ == '__main__':
    main()

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

csr = csr_matrix(C)
SP = shortest_path(csr)
#print(SP)
#print(csr)
#print(shortest_path(csr))

dicA = {}
for i in range(H):
  for j in range(W):
    if A[i][j] != -1 and A[i][j] != 1:
      if A[i][j] in dicA:
        dicA[A[i][j]] += 1
      else:
        dicA[A[i][j]] = 1
#print(dicA)

ans = 0
for key,val in dicA.items():
  ans += SP[key][1] * val
print(int(ans))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
cost=[]
ans=[0]*10
for _ in range(10):
	x=list(map(int,input().split()))
	cost.append(x)
for _ in range(h):
	x=list(map(int,input().split()))
	for j in range(10):
		ans[j]+=x.count(j)

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=10
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
p=0
for i in range(10):
	p+=ans[i]*warshall_floyd(cost)[i][1]
print(p)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall

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

C = floyd_warshall(C)

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

print(int(ans))

Submission status: Accepted

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

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 row in a:
    for ele in row:
        if ele == -1:
            continue
        else:
            ans += c[ele][1]

print(ans)

Submission status: Accepted

Solution code:
def warsha_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])
                # "今現在求まっているiからjへの最短距離"と"今現在求まっているiからkへの最短距離 + 今現在求まっているkからjへの最短距離 の和"を比較する
    return d


H, W = map(int, input().split())  # H行, W列のgridgraph
N = 10
C = [list(map(int, input().split())) for _ in range(N)]  # 0~9 と 0~9の二重リスト
# C[u][v] := 辺uvのコスト
A = [list(map(int, input().split())) for _ in range(H)]

C = warsha_floyd(C)

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 heapq

H,W = map(int,input().split())
C = [[int(x) for x in input().split()] for _ in range(10)]
num = [0] * 10
for _ in range(H):
    for x in input().split():
        if int(x) != -1:
            num[int(x)] += 1

que = []
flag = [True]*10
flag[1] = False
cost = [10**10]*10
cost[1] = 0

for i in range(10):
    if flag[i]:
        heapq.heappush(que,[C[i][1],i])

while que:
    a,b = heapq.heappop(que)
    if flag[b]:
        flag[b] = False
        cost[b] = a
        for i in range(10):
            if flag[i]:
                heapq.heappush(que,[C[i][b]+a,i])

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

Submission status: Accepted

Solution code:
import copy

def main():
    H,W = map(int, input().split())
    c = [[int(i) for i in input().split()] for i in range(10)]
    a = [[int(i) for i in input().split()] for i in range(H)]
    #d = copy.deepcopy(c)

    # ワーシャルフロイド法
    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:
        for j in i:
            if j > 1 or j == 0:
                ans += c[j][1]
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy

def main():
    H,W = map(int, input().split())
    c = [[int(i) for i in input().split()] for i in range(10)]
    a = [[int(i) for i in input().split()] for i in range(H)]
    d = copy.deepcopy(c)

    # ワーシャルフロイド法
    for k in range(10):
        for i in range(10):
            for j in range(10):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    
    ans = 0
    for i in a:
        for j in i:
            if j > 1 or j == 0:
                ans += d[j][1]
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H,W = map(int, input().split())
c, A = [], []
num = [0] * 10
for _ in range(10):
    ci = list(map(int, input().split()))
    ci[0], ci[1] = ci[1], ci[0]
    c.append(ci)
for _ in range(H):
    A += list(map(int, input().split()))
for i in [0] + list(range(2, 10)):
    num[i] += A.count(i)

c = [[0]] + c[:1] + c[2:]
num[0], num[1] = num[1], num[0]

dp = [[c[i][0] for i in range(10)]] + [[10000 for i in range(10)] for j in range(9)]
for i in range(1, 10):
    for j in range(1, 10):
            dp[i][j] = min(c[j][k] + dp[i-1][k] for k in range(1, 10))

print(sum(dp[9][i] * num[i] for i in range(1,10)))

Submission status: Accepted

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

ans=0

for i in range(h):
  li=list(map(int,input().split()))
  for a in li:
    if a!=-1:
      ans+=c[a][1]
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=[list(map(int, input().split())) for i in range(10)]
l=[None]*10
for i in range(10):
    l[i]=S[i][1]
for i in range(5):
    for j in range(10):
        for k in range(10):
            if l[j]>l[k]+S[j][k]:
                l[j]=l[k]+S[j][k]
l.append(0)
a=0
for i in range(H):
    L=list(map(int,input().split()))
    for j in L:
        a+=l[j]
print(a)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=[list(map(int, input().split())) for i in range(10)]
l=[None]*10
for i in range(10):
    l[i]=S[i][1]
for i in range(6):
    for j in range(10):
        for k in range(10):
            if l[j]>l[k]+S[j][k]:
                l[j]=l[k]+S[j][k]
l.append(0)
a=0
for i in range(H):
    L=list(map(int,input().split()))
    for j in L:
        a+=l[j]
print(a)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=[list(map(int, input().split())) for i in range(10)]
l=[None]*10
for i in range(10):
    l[i]=S[i][1]
for i in range(7):
    for j in range(10):
        for k in range(10):
            if l[j]>l[k]+S[j][k]:
                l[j]=l[k]+S[j][k]
l.append(0)
a=0
for i in range(H):
    L=list(map(int,input().split()))
    for j in L:
        a+=l[j]
print(a)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=[list(map(int, input().split())) for i in range(10)]
l=[None]*10
for i in range(10):
    l[i]=S[i][1]
for i in range(8):
    for j in range(10):
        for k in range(10):
            if l[j]>l[k]+S[j][k]:
                l[j]=l[k]+S[j][k]
l.append(0)
a=0
for i in range(H):
    L=list(map(int,input().split()))
    for j in L:
        a+=l[j]
print(a)

Submission status: Accepted

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

# 頂点数 v のグラフ d の頂点 i から頂点 j への最短路を求める
def warchall_floyd(d, v):
    for k in range(v):
        for i in range(v):
            for j in range(v):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
def main():
    H,_ = map(int, input().split())
    C = []
    A = []
    for _ in range(10):
        C.append(list(map(int, input().split())))
    for _ in range(H):
        A.append(list(map(int, input().split())))
    
    warchall_floyd(C, 10)

    ans = 0
    for a in A:
        for x in a:
            if x != -1:
                ans += C[x][1]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def dijkstra_heap(s, n, edge):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


def main():
    H, W = map(int, input().split())

    edge = [[] for i in range(10)]
    for i in range(10):
        C = list(map(int, input().split()))
        for j in range(10):
            if i==j:
                continue
            edge[i].append([C[j],j])

    MP = [0]*10
    for i in range(10):
        if i==1:
            continue
        D = dijkstra_heap(i, 10, edge)
        MP[i] = D[1]

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

h, w = map(int, input().split())
cs = [list(map(int, input().split())) for _ in range(10)]
counter = collections.Counter()
for _ in range(h):
    for x in map(int, input().split()):
        if x != -1:
            counter[x] += 1

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

res = 0
for k, v in counter.items():
    res += cs[k][1] * v
print(res)