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:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    h,w = i_map()
    c = [i_list() 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 h in range(h):
        a = i_list()
        for b in a:
            if b>=0:
                ans += c[b][1]
    print(ans)



if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
"""
きょうぎぷろぐらみんぐ！！！！！！
競プロ競プロ競プロ競プロ競プロ競プローーーーー！！！！！！！
hshs！！ﾊｱﾊｱ！！興奮興奮！！！！うおおおおおおお！！！
競プロの重要性！！ｺﾞﾝｺﾞﾝｺﾞﾝｺﾞﾝ(頭を難易度の壁に打ち付ける音)
うおおおおおおお！！競プロの重要性！！
"""
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
h,w=map(int,input().split())
num=[list(map(int,input().split())) for _ in range(10)]
num=csr_matrix(num)
ans=shortest_path(num)
ans=ans.tolist()
ans2=[0]*10
for i in range(10):
    ans2[i]=int(ans[i][1])
ans3=0
for i in range(h):
    a=list(map(int,input().split()))
    for j in range(w):
        if a[j]!=-1:
            ans3+=ans2[a[j]]
print(ans3)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
if __name__ == "__main__":
    H,W = map(int,input().split())
    V = 10
    edges = []
    for i in range(10):
        c = list(map(int,input().split()))
        edges.append([(j,c[j]) for j in range(10)])
    INF = float("inf")
    dp = [[INF]*V for _ in range(V)]
    for i in range(V):
        for j, w in edges[i]:
            dp[i][j] = w

    for k in range(V):
        for i in range(V):
            for j in range(V):
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
    ans = 0
    for _ in range(H):
        for x in map(int,input().split()):
            if x >= 0:
                ans += dp[x][1]
    print(ans)

Submission status: Accepted

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

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

C = w_f(C)

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

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:
from numpy import *
from scipy.sparse.csgraph import *
H,W = map(int,input().split())
G = array([list(map(int,input().split())) for n in range(10)])
A = [list(map(int,input().split())) for h in range(H)]
F = shortest_path(G)
ans = 0

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

print(int(ans))

Submission status: Accepted

Solution code:
INF=float('inf')
h,w=map(int,input().split())
dist=[[0 for i in range(10)]for j in range(10)]
for i in range(10):
  s=list(map(int,input().split()))
  for j in range(10):
    if i==j:
      continue
    dist[i][j]=s[j]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#c[i][j]=数字iから数字jにかえるのに必要な最小の魔力
H,W=list(map(int,input().split()))
c=[[i for i in range(10)] for j in range(10)]
for i in range(10):
  s=list(map(int,input().split()))
  for j in range(10):
    c[i][j]=s[j]

#ワーシャルフロイド法
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):
  a=list(map(int,input().split()))
  for j in range(W):
    if a[j]!=-1:
      ans=ans+c[a[j]][1]
print(ans)

Submission status: Accepted

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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

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

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

res = 0
for h in range(H):
    A = list(map(int, input().split()))
    for a in A:
        if a != -1:
            res += edge[a][1]

print(res)

Submission status: Accepted

Solution code:
import numpy as np
H, W = (int(x) for x in input().split())
C = np.array([[int(x) for x in input().split()] for _ in range(10)])
A = [[int(x) if int(x) >= 0 else 1 for x in input().split()] for _ in range(H)]
from scipy.sparse.csgraph import dijkstra
C = dijkstra(C,directed=True) #有向グラフの経路圧縮（ダイクストラ法）
ans = sum(sum(C[x,1] for x in A))
print(int(ans))

Submission status: Accepted

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

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

d = copy(data)
def cnt_set(d):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
cnt_set(d)
ans = 0

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

print(ans)

Submission status: Accepted

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

for k in range(10):
  for i in range(10):
    for j in range(10):
      mp[i][j] = min(mp[i][j], mp[i][k]+mp[k][j])
    
rlt = 0
for i in range(H):
  for j in map(int, input().split()):
    if j != -1 and j != 1:
      rlt += mp[j][1]
      
print(rlt)

Submission status: Accepted

Solution code:
from collections import Counter
H,W=list(map(int, input().split()))
C=[list(map(int, input().split())) for _ in range(10)]
A=Counter()
for _ in range(H):
    A+=Counter(list(map(int, input().split())))
del A[-1]
# print(A)
# Warshall–Floydを使います

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

ans=0
for i in A:
    ans+=C[i][1]*A[i]
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

H,W = I()
cost = [l() for _ in range(10)]
A = [l() for _ in range(H)]
ans = 0
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])
for i in range(H):
    for j in range(W):
        if A[i][j] > -1:
            ans += cost[A[i][j]][1]
print(ans)

Submission status: Accepted

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

H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(10)]
A = [list(map(int, input().split())) for _ in range(H)]
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:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


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


# In[3]:


def wf_func(mat):
    dist = mat
    for k in range(10):
        for i in range(10):
            for j in range(10):
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
    return dist


# In[5]:


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


# In[ ]:

Submission status: Accepted

Solution code:
"""ABC079D Wall 別解
ワーシャルフロイドでやった場合
"""

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

counter = {i: 0 for i in range(-1, 10)}
for i in range(H):
    tmp = list(map(int, input().split()))
    for j in range(W):
        counter[tmp[j]] += 1

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

ans = sum([counter[i]*dp[i][1] for i in range(10)])
print(ans)

Submission status: Accepted

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

counter = {i: 0 for i in range(-1, 10)}
for i in range(H):
    tmp = list(map(int, input().split()))
    for j in range(W):
        counter[tmp[j]] += 1
MAX = 10**4
INF = float("inf")
def f(start):
    if start == 1:
        return 0
    dp = [[INF]*MAX for _ in range(10)]
    dp[start][0] = 0
    for i in range(1, MAX):
        for new in range(10):
            dp[new][i] = min(dp[num][i-1] + c[num][new] for num in range(10))
    return min(dp[1])

ans = 0
for i in range(10):
    if counter[i] == 0:
        continue
    else:
        ans += counter[i] * f(i)
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
weight=[list(map(int,input().split())) for _ in range(10)]
graph=[[i for i in range(10)] for j in range(10)]
for i in range(10):
  graph[i].pop(i)
import math
import heapq

d=[math.inf for i in range(10)]
d[1]=0
q=[]
heapq.heappush(q,1)
while q:
  v=heapq.heappop(q)
  for u in graph[v]:
    if weight[u][v]+d[v]<d[u]:
      d[u]=weight[u][v]+d[v]
      heapq.heappush(q,u)
A=[list(map(int,input().split())) for _ in range(H)]

dic={}
for i in range(H):
  for j in range(W):
    if A[i][j]!=-1:
      if A[i][j] in dic:
        dic[A[i][j]]+=1
      else:
        dic[A[i][j]]=1
ans=0
for k,v in dic.items():
  ans+=d[k]*v
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 aa in A:
    for a in aa:
        if a==-1:
            ans+=0
        else:
            ans+=C[a][1]
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline
H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in [0]*10]
A = map(int, read().split())

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

cnt = [0]*10
for a in A:
    if a != -1:
        cnt[a] += 1
ans = 0
for i, c in enumerate(cnt):
    ans += C[i][1] * c
print(ans)

Submission status: Accepted

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

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

# 0-9を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])

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

print(count)

Submission status: Accepted

Solution code:
def warshall_floyd(d):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
 
 
h, w = list(map(int, input().split())) 
 
power = [list(map(int, input().split())) for i in range(10)] 

power = warshall_floyd(power)

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

# Dijkstra法で1からの距離を求める
INF = 10**12
q = [(0,1)] # 始点のコストとindex
d = [INF] * 10
d[1] = 0

while len(q) > 0:
    cost, u = heappop(q)
    #print(u,c[u])
    for v in range(10):
        if v == u: continue
        #print(i,v)
        tmp = d[u] + c[v][u]
        #print(v,tmp)
        if tmp < d[v]:
            d[v] = tmp
            heappush(q, (d[v], v))
    #print(d)

A =  [0]*10
for i in range(H):
    tmp = list(map(int, input().split()))
    for j in range(W):
        if tmp[j] >= 0:
            A[tmp[j]] += 1

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

Submission status: Accepted

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

#d = [[INF]*10 for _ in range(10)]
#print(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])
#print(c)
ans = 0
for i in range(H):
  temp = list(map(int,input().split()))
  for j in range(W):
    if temp[j] == -1:
      continue
    ans += c[temp[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)]
dist = [[0 for _ in range(10)] for _ in range(10)]
for i in range(10):
    for j in range(10):
        dist[i][j] = C[i][j]
for k in range(10):
    for i in range(10):
        for j in range(10):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
cnt = 0
for i in range(H):
    for j in range(W):
        if A[i][j]>=0:
            cnt += dist[A[i][j]][1]
print(cnt)

Submission status: Accepted

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

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

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

ans = 0
for i in range(h):
    ans += sum(map(lambda x: g[x][1],
                   filter(lambda x: x != -1, map(int, input().split()))))
print(ans)

Submission status: Accepted

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


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

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

Submission status: Accepted

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

                
from collections import Counter

INF = float('inf') 
H, W = map(int, input().split())
d =[[int(i) for i in input().split()] for _ in range(10)]  #; print(d)
a = []
for _ in range(H):
    a.extend([int(i) for i in input().split() if i != '-1'])
dic = Counter(a)     #; print(a); print(dic) 

warshall_floyd(10)   #; print(d)

ans = 0
for key, val in dic.items():
    ans += d[key][1] * val   #; print(key, d[key][1], val)

print(ans)

Submission status: Accepted

Solution code:
from itertools import chain
import numpy as np
import networkx as nx

h, w, *X = map(int, open(0).read().split())
C = np.array(X[:100], dtype=int).reshape((10, 10))
A = np.array(X[100:], dtype=int).reshape((h, w))

G = nx.DiGraph(C)
d = {-1:0}
for i in range(10):
    d[i] = nx.shortest_path_length(G, i, 1, weight='weight')
print(sum(d[a] for a in chain.from_iterable(A)))

Submission status: Accepted

Solution code:
from itertools import chain
import numpy as np
import networkx as nx

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
C = np.zeros((10, 10), dtype=int)
for i in range(10):
    for j, c in enumerate(map(int, next(X).split())):
        C[i, j] = c
A = np.zeros((h, w), dtype=int)
for i in range(h):
    for j, a in enumerate(map(int, next(X).split())):
        A[i, j] = a

G = nx.DiGraph(C)
d = {-1:0}
for i in range(10):
    d[i] = nx.shortest_path_length(G, i, 1, weight='weight')
print(sum(d[a] for a in chain.from_iterable(A)))

Submission status: Accepted

Solution code:
from itertools import chain
import numpy as np
import networkx as nx

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
C = np.zeros((10, 10), dtype=int)
for i in range(10):
    for j, c in enumerate(map(int, next(X).split())):
        C[i, j] = c
A = np.zeros((h, w), dtype=int)
for i in range(h):
    for j, a in enumerate(map(int, next(X).split())):
        A[i, j] = a

G = nx.DiGraph(C)
d = {}
for i in range(10):
    if i == 1:
        continue
    d[i] = nx.shortest_path_length(G, i, 1, weight='weight')

s = 0
for a in chain.from_iterable(A):
    if a == -1 or a == 1:
        continue
    s += d[a]
print(s)

Submission status: Accepted

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

inf = 10 ** 20
d = [list(map(int, input().split())) for _ 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])

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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right



def solve():
    H, W = MI()
    dist = LLI(10)
    N = 10

    # dist = [[INF]*10 for _ in range(10)]
    # for i in range(N):
    #     dist[i][1] = C[i, 1]

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = 0
    for i in range(H):
        for r in LI():
            if r != -1:
                ans += dist[r][1]
    print(ans)




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

cost = [[float("inf")]*10 for _ in range(10)]
#cost[k][i][j]はｋ個までの頂点を経由して、頂点iから頂点jへ行くときの最小コスト
#cost[0][i][j]は何も経由しないのでc_ijと等しい
#ｋのところは省略できる
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])
#print(cost)
ans = 0
for i in range(h):
    for j in range(w):
        a_ij = a[i][j]
        if a_ij == -1 or a_ij == 1:
            continue
        ans += cost[a_ij][1]
print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd():
    for middle in range(10):
        for start in range(10):
            for end in range(10):
                costs[start][end] = min(costs[start][end], costs[start][middle] + costs[middle][end])


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

for i in range(10):
    costs.append(list(map(int, input().split())))

warshall_floyd()

# print(*costs, sep='\n')
ans = 0
for i in range(H):
    wall = list(map(int, input().split()))
    for num in wall:
        if num != -1:
            ans += costs[num][1]
print(ans)

Submission status: Accepted

Solution code:
def floyd_warshall(dist):
    v = len(dist)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])

h,w = map(int,input().split())
c = [list(map(int,input().split())) for _ in range(10)]
floyd_warshall(c)
A = [list(map(int,input().split())) for _ in range(h)]
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 shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

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

csr = csr_matrix(c)

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

cost = floyd_warshall(csr)[:,1]

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

Submission status: Accepted

Solution code:
import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * 10 # 行ったことのないところは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

h,w = map(int,input().split())
e = [[] for _ in range(10)]
for i in range(10):
    alist = list(map(int,input().split()))
    for j in range(10):
        if i != j:
            e[i].append((alist[j], j))


l = []
for i in range(h):
    for a in list(map(int,input().split())):
        if a != -1:
            l.append(a)

ans = 0
for i in l:
    ans += dijkstra(i)[1]
print(ans)

Submission status: Accepted

Solution code:
class Digraph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=set(vertex)

        self.edge_number=0
        self.vertex_number=len(vertex)

        self.adjacent_out={v:{} for v in vertex} #出近傍(vが始点)
        self.adjacent_in={v:{} for v in vertex} #入近傍(vが終点)

    #頂点の追加
    def add_vertex(self,*adder):
        for v in adder:
            if v not in self.vertex:
                self.adjacent_in[v]={}
                self.adjacent_out[v]={}

                self.vertex_number+=1
                self.vertex.add(v)

    #辺の追加(更新)
    def add_edge(self,From,To,weight=1):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To not in self.adjacent_in[From]:
            self.edge_number+=1

        self.adjacent_out[From][To]=weight
        self.adjacent_in[To][From]=weight

    #辺を除く
    def remove_edge(self,From,To):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(w)

        if To in self.adjacent_out[From]:
            del self.adjacent_out[From][To]
            del self.adjacent_in[To][From]
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*vertexes):
        for  v in vertexes:
            if v in self.vertex:
                self.vertex_number-=1

                for u in self.adjacent_out[v]:
                    del self.adjacent_in[u][v]
                    self.edge_number-=1
                del self.adjacent_out[v]

                for u in self.adjacent_in[v]:
                    del self.adjacent_out[u][v]
                    self.edge_number-=1
                del self.adjacent_in[v]

    #Walkの追加
    def add_walk(self,*walk):
        pass

    #Cycleの追加
    def add_cycle(self,*cycle):
        pass

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.vertex

    #グラフに辺が存在するか否か
    def edge_exist(self,From,To):
        if not(self.vertex_exist(From) and self.vertex_exist(To)):
            return False
        return To in self.adjacent_out[From]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #出次数
    def out_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_out[v])

    #入次数
    def in_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_in[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return self.out_degree(v)-self.in_degree(v)

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        pass

def Dijkstra_All(D,From,with_path=False):
    """Dijksta法を用いて,単一始点Fromからの距離を求める.

    D:辺の重みが全て非負の有向グラフ
    From:始点
    To:終点
    with_path:最短路も含めて出力するか?

    (出力の結果)
    with_path=True->(距離,最短経路の辿る際の前の頂点)
    with_path=False->距離
    """
    from copy import copy
    from heapq import heappush,heappop

    T={v:float("inf") for v in D.vertex}
    T[From]=0

    if with_path:
        Prev={v:None for v in D.vertex}

    Q=[(0,From)]

    while Q:
        c,u=heappop(Q)

        if T[u]<c:
            continue

        for v in D.adjacent_out[u]:
            if T[v]>T[u]+D.adjacent_out[u][v]:
                T[v]=T[u]+D.adjacent_out[u][v]
                heappush(Q,(T[v],v))

                if with_path:
                    Prev[v]=u

    if with_path:
        return (T,Prev)
    else:
        return  T

#逆グラフの作成
def Inverse_Graph(D):
    """有向グラフDの全ての辺の向きを変えたグラフを出力する.

    D:有向グラフ
    """
    from copy import deepcopy

    F=Digraph(D.vertex)

    F.edge_number=D.edge_number
    F.vertex_number=D.vertex_number

    F.adjacent_in=deepcopy(D.adjacent_out)
    F.adjacent_out=deepcopy(D.adjacent_in)

    return F

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

D=Digraph(range(10))
for i in range(10):
    C=list(map(int,input().split()))
    for j in range(10):
        D.add_edge(i,j,C[j])

D=Inverse_Graph(D)
T=Dijkstra_All(D,1)

Count={x:0 for x in range(-1,10)}

for _ in range(H):
    A=list(map(int,input().split()))
    for a in A:
        Count[a]+=1

X=0
for a in range(10):
    X+=Count[a]*T[a]

print(X)