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 sys

sys.setrecursionlimit(1000000)


def z(changeable: [], cc: [], ans_set):
    for nums, limit_c in changeable:
        # 最新のもの
        num = nums[-1]
        next_ls = []
        target = cc[num]
        limit = limit_c

        if target[1] < limit:
            limit = target[1]
            sub = target[1]
            for i in range(len(nums)-1):
                sub += cc[nums[i]][nums[i+1]]
            ans_set.add(sub)

        for i in range(10):
            if i in nums:
                continue
            x = target[i]
            if x < limit:
                nums_cp = nums[:]
                nums_cp.append(i)
                next_ls.append((nums_cp, limit - x))
        z(next_ls, cc, ans_set)


def main():
    h, w = map(int, input().split())
    cc = []
    for i in range(10):
        ls = list(map(int, input().split()))
        cc.append(ls)

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

    # 1になるまでの最小値
    to1dic = {}
    for i in range(10):
        if i == 1:
            continue
        target = cc[i]
        # 初期値は直接変換。これよりも小さい数でいけたらそれにする
        limit = target[1]
        changeables = []
        ans_set = {limit}
        for j in range(10):
            if j == i:
                continue
            x = target[j]
            if x < limit - 1:
                changeables.append(([i, j], limit - x))

        z(changeables, cc, ans_set)

        min_v = min(ans_set)

        to1dic.setdefault(i, min_v)

    total = 0
    for i in range(h):
        for j in range(w):
            num = wall[i][j]
            if num == -1 or num == 1:
                continue
            total += to1dic[num]
    # print(to1dic)
    print(total)


main()

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

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

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

    # 頂点kを経由する場合としない場合を比較
    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 a in A:
        for i in a:
            if i != -1 and i != 1:
                ans += C[i][1]

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    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 or A[i][j] == 1):
                continue
            ans += c[A[i][j]][1]
    print(ans)    
main()

Submission status: Accepted

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

dist = [[float('inf')] * 10 for i in range(10)]
for i in range(10):
    c = list(map(int, input().split()))
    for j in range(10):
        dist[i][j] = c[j]

# warshall_floydを回してdistを改良
def warshall_floyd(dist):
    for k in range(10):
        # i:start j:goal k:中間地点でループ回す
        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
warshall_floyd(dist)

board = [list(map(int, input().split())) for i in range(n)]

cnt = 0
for row in board:
    for i in row:
        if (i == -1) or (i == 1):
            continue
        else:
            cnt += dist[i][1]
print(cnt)

Submission status: Accepted

Solution code:
from itertools import *
H,W=map(int,input().split())
c=[list(map(int,input().split())) for i in range(10+H)]
for k,i,j in product(list(range(10)),repeat=3):
    c[i][j]=min(c[i][j],c[i][k]+c[k][j])
print(sum(c[c[i+10][j]][1] if c[i+10][j]!=-1 else 0 for j in range(W) for i in range(H)))

Submission status: Accepted

Solution code:
import itertools
H,W=map(int,input().split())
c=[list(map(int,input().split())) for i in range(10)]
A=[list(map(int,input().split())) for i in range(H)]
for k,i,j in itertools.product(list(range(10)),repeat=3):
    c[i][j]=min(c[i][j],c[i][k]+c[k][j])
res=sum(c[A[i][j]][1] if A[i][j]!=-1 else 0 for j in range(W) for i in range(H))
print(res)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
import math
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
#import numpy as np
#INF = float("inf")
H,W = map(int,input().split())#頂点、辺の数
INF = float("inf")
cost = [list(map(int,input().split())) for _ in range(10)]
#実装
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])
s = 0
for _ in range(H):
    A = list(map(int,input().split()))
    for k in A:
        if k == -1:
            continue
        s += cost[k][1]
print(s)

Submission status: Accepted

Solution code:
import sys

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


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

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

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

    print(ans)


if __name__ == '__main__':
    resolve()

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())
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
load = []
for i in range(10):
  load.append(list(map(int,input().split())))
load = np.array(load)
dist = shortest_path(load)
count = 0
for i in range (h):
  h_list = list(map(int,input().split()))
  for j in range(w):
    if h_list[j] != -1:
      count += dist[h_list[j]][1]

print(int(count))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
#import queue
from copy import copy, deepcopy
from operator import itemgetter

from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)
#from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
#dequeを使うときはpython3を使う、pypyはダメ
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
import heapq
#q=heapq.heapify(l),heappush(q,a),heappop(q)

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds

#mod = 10**9+7

#N = int(input())
H, W = map(int, input().split())
c=[[] for i in range(10)]
for j in range(10):
    cj=list(map(int, input().split()))
    for i in range(10):
        c[i].append(cj[i])

#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [inputl() for i in range(H)]


#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入

tdis=[10**5]*10
dis=0
#tdis[0]=0

q=[(0,1)]
#print(q)
heapq.heapify(q)
while len(q):
    #print(q)
    d, v=heapq.heappop(q)
    if tdis[v] <10**5:
        continue
    tdis[v]=d
    for i in range(10):
        heapq.heappush(q,(d+c[v][i],i))

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

Submission status: Accepted

Solution code:
from scipy import sparse
import numpy as np
from collections import Counter
import itertools
H,W = (int(x) for x in input().split())
b = []
wall = []
ans = 0
for i in range(10):
    b.append(list(map(int, input().split())))
c = np.array(b)
w = sparse.csgraph.floyd_warshall(c)
wall = [map(int, input().split()) for _ in range(H)]
count = Counter(list(itertools.chain.from_iterable(wall)))
for item in count.items():
    if item[0] == -1:
        continue
    else:
        ans += item[1] * w[item[0]][1]
print(int(ans))

Submission status: Accepted

Solution code:
H,W = map(int,(input().split()))
c = [[] for _ in range(10)]
for i in range(10):
    c[i] = list(map(int,(input().split())))
a = [[] for _ in range(H)]
for i in range(H):
    a[i] = list(map(int,(input().split())))
        
dist = [[float("inf")]*10 for _ in range(10)]
for i in range(10):
    for j in range(10):
        dist[i][j] = c[i][j]

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

dist = warshall_floyd(dist)

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

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
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 funci(d,j):
    ret=0
    for i in range(len(d)-1):
        ret+=c[d[i]][d[i+1]]
    ret+=c[d[-1]][j]
    return ret

def bfs(i):#i!=1,i->1 minimum
    ret=c[i][1]
    todo=deque([[i,j] for j in range(10) if j!=i and j!=1])
    while len(todo)>0:
        d=todo.popleft()
        ret=min(ret,funci(d,1))
        for k in [j for j in range(10) if j not in d and j!=1]:
            f=d.copy()
            x=funci(f,k)
            if funci(f,k)<ret:
                f.append(k)
                todo.append(f)
    return ret
g=[bfs(i)for i in range(10)]
ans=0
for ai in a:
    for aij in ai:
        ans+=g[aij] if aij != -1 else 0
print(ans)
#print(g)

Submission status: Accepted

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

Submission status: Accepted

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

for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])
ans = 0
for i in range(h):
    for j in range(w):
        if wa[i][j]!=1 and wa[i][j]!=-1:
            ans+=c[wa[i][j]][1]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import permutations
h,w=map(int,input().split())
d=[list(map(int,input().split())) for i in range(10)]

def warshall_floyd(d):
    n=len(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
d=warshall_floyd(d)
cost=[d[i][1] for i in range(10)]

from collections import defaultdict
count=defaultdict(int)
for i in range(h):
    A=list(map(int,input().split()))
    for a in A:
        count[a]+=1

ans=0
t=[x for x in range(10) if x!=1]
for i in t:
    ans+=cost[i]*count[i]
print(ans)

Submission status: Accepted

Solution code:
import sys

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

for i in range(10):
    for j in range(10):
        for k in range(10):
            c[j][k] = min(c[j][k], c[j][i] + c[i][k])
magic = [c[i][1] for i in range(10)]
ans = 0
for _ in range(H):
    row = map(int, readline().split())
    ans += sum(magic[i] for i in row if i != -1)
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
wlist=[list(map(int,input().split()))for _ in range(10)]
for i in range(10):
    for j in range(10):
        for k in range(10):
            wlist[j][k]=min(wlist[j][k],wlist[j][i]+wlist[i][k])
ans=0
for _ in range(h):
    t=list(map(int,input().split()))
    for i in t:
        if i==-1 or i==1:
            continue
        else:
            ans+=wlist[i][1]
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
h,w=map(int,input().split())
es=[[] for i in range(10)]

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

n=10
import heapq

def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in es[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 es[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

cost=[dijkstra_heap(i)[1] for i in range(10)]

from collections import defaultdict
count=defaultdict(int)
for i in range(h):
    A=list(map(int,input().split()))
    for a in A:
        count[a]+=1

ans=0
t=[x for x in range(10) if x!=1]
for i in t:
    ans+=cost[i]*count[i]
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
h,w=map(int,input().split())
C=[list(map(int,input().split())) for i in range(10)]

cost=[C[i][1] for i in range(10)]
for i in range(10):
    if i!=1:
        keiyu=[x for x in range(10) if x!=1 and x!=i]
        for j in range(9):
            perm=permutations(keiyu,r=j)
            for k in perm:
                k=[i]+list(k)+[1]
                tmp=0
                for l in range(len(k)-1):
                    tmp+=C[k[l]][k[l+1]]
                cost[i]=min(tmp, cost[i])

from collections import defaultdict
count=defaultdict(int)
for i in range(h):
    A=list(map(int,input().split()))
    for a in A:
        count[a]+=1

ans=0
t=[x for x in range(10) if x!=1]
for i in t:
    ans+=cost[i]*count[i]
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())

def warshall_floyd(vl,d):
  #d[i][j]: iからjへの最短距離
  for vk in vl:
    for vi in vl:
      for vj in vl:
        if vk in d[vi] and vj in d[vk]:
          d[vi][vj]=min(d[vi][vj],d[vi][vk]+d[vk][vj])
  return d

cmat=[]
for i in range(10):
  cmat.append([int(c) for c in input().split()])
#print(cmat)

amat=[]
for i in range(H):
  amat.append([int(a) for a in input().split()])
#print(amat)

vlist=list(range(10))
dist={}
for vi in vlist:
  dist[vi]={vi:0}
  for vj in vlist:
    dist[vi][vj]=cmat[vi][vj]
#print(dist)

dist=warshall_floyd(vlist,dist)
#print(dist)
    
answer=0
for i in range(H):
  for j in range(W):
    if amat[i][j]==-1:
      continue
    answer+=dist[amat[i][j]][1]
    
print(answer)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())

import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  dist,used={},{}
  for v in vlist:
    dist[v]=float("inf")
    used[v]=False
  dist[s]=0
  used[s]=True

  hq_edge=[]
  for v,w in edge[s]:
    heapq.heappush(hq_edge,(w,v))

  while len(hq_edge):
    min_w,min_v=heapq.heappop(hq_edge)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if used[min_v]:
      continue

    dist[min_v]=min_w
    used[min_v]=True
    for v,w in edge[min_v]:
      if not used[v]:
        heapq.heappush(hq_edge,(min_w+w,v))

  return dist

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

amat=[]
for i in range(H):
  amat.append(list(map(int,input().split())))
#print(amat)

vlist=list(range(10))
edge={}
for i in range(10):
  edge[i]=[]
  for j in range(10):
    edge[i].append((j,cmat[i][j]))
    
mindist=[10**9]*10
for i in range(10):
  res=dijkstra_heap(i)
  #print(i,res)
  mindist[i]=res[1]
#print(mindist)

answer=0
for i in range(H):
  for j in range(W):
    if amat[i][j]==-1:
      continue
    answer+=mindist[amat[i][j]]
    
print(answer)

Submission status: Accepted

Solution code:
def warshalFloyd():
    G=[list(map(int,input().split())) for _ in range(10)]

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

    return G


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

ans=0
for i in range(h):
    for j in list(map(int,input().split())):
        if j==-1:continue
        else:ans +=Graph[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,csgraph_from_dense
from scipy.sparse import csr_matrix

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

g=csr_matrix(c)
paths=shortest_path(g,method="FW")

cost=0
for i in range(h):
    for j in range(w):
        if a[i][j]!=-1 and a[i][j]!=1:
            cost+=int(paths[a[i][j]][1])

print(cost)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    # 最短経路問題で使われるアルゴリズムの１つ。
    # グラフ上の全ての頂点間の最短経路を探す
    # 負の閉路（辺の重みの和が負になるような閉路）がない限り、負の辺があっても使える。

    # 負の閉路を持つ場合は'NEGATIVE CYCLE'を、そうでない場合には(i,j)成分に
    # 頂点iから頂点jへの最短経路の距離を格納するdist_listをprintする関数
    def warshall_floyd(v_num, dist_lst):
        # 負の閉路を持つか
        negative_cycle_flag = False

        # 頂点iから頂点jへの経路と、頂点kを経由した場合の経路とを比較して
        # よりコストの合計が小さい方を配列に入れる動的計画法
        for k in range(v_num):
            for i in range(v_num):
                for j in range(v_num):
                    # i→k→jがつながっててしかもi→jルートよりもイケてるなら更新
                    if dist_lst[i][k] != INF and dist_lst[k][j] != INF:
                        if dist_lst[i][j] > dist_lst[i][k] + dist_lst[k][j]:
                            dist_lst[i][j] = dist_lst[i][k] + dist_lst[k][j]

        for v in range(v_num):
            # dist_lstに負の数が格納されているとは、
            # グラフが負の閉路を持つことを意味する
            if dist_lst[v][v] < 0:
                negative_cycle_flag = True

        return dist_lst

    H, W = map(int, input().split())
    # 頂点の数と辺の数
    v_num, e_num = 10, 100

    # 配列dist_lst[a][b]には頂点a,b間の辺のコストを入れておき、
    # a=bの時は0を、a,b間の辺が存在しないときはINFを入れておく。
    INF = 10 ** 20
    dist_lst = [[INF] * v_num for _ in range(v_num)]

    costs = [[i for i in list(map(int, input().split()))] for _ in range(10)]
    for s in range(10):
        for t in range(10):
            dist_lst[s][t] = costs[s][t]

    dist_lst = warshall_floyd(v_num, dist_lst)
    wall = [[i for i in list(map(int, input().split()))] for _ in range(H)]
    cnt = 0
    for h in range(H):
        for w in range(W):
            val = wall[h][w]
            if val != -1:
                cnt += dist_lst[val][1]
    print(cnt)


resolve()

Submission status: Accepted

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


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

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

    dist_matrix = floyd_warshall(csgraph=graph, directed=True, return_predecessors=False)
    dist_matrix = list(dist_matrix)

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

    cnt = 0
    for h in range(H):
        for w in range(W):
            val = wall[h][w]
            if val != -1 and val != 1:
                cnt += dist_matrix[val][1]
    print(int(cnt))


resolve()

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
c = [list(map(int,input().split())) for i in range(10)]
d = [0]*10
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        if A[j]!=-1:
            d[A[j]] += 1

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

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

Submission status: Accepted

Solution code:
def dijkstra(s,n,cost):
  d=[float('inf')]*n
  visited=[0]*n
  d[s]=0
  while True:
    v=-1
    for i in range(n-1,-1,-1):
      if visited[i]==0 and v==-1:
        v=i
      elif visited[i]==0 and d[i]<d[v]:
        v=i
    if v==-1:
      break
    visited[v]=1
    for j in range(n-1,-1,-1):
      d[j]=min(d[j],d[v]+cost[j][v])
  return d

h,w=map(int,input().split())
c=[list(map(int,input().split())) for _ in range(10)]
a=[list(map(int,input().split())) for _ in range(h)]
cost=dijkstra(1,10,c)
ans=0
for i in range(h):
  for j in range(w):
    ans+=(cost[a[i][j]] if a[i][j]>-1 else 0)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
from collections import deque

# sys.setrecursionlimit(100001)
INF = sys.maxsize


# ===CODE===
def main():
    ten = 10
    h,w = map(int, input().split())
    dist_mat=[]
    for i in range(ten):
        l = list(map(int, input().split()))
        dist_mat.append(l)

    table = []

    for i in range(h):
        l = list(map(int, input().split()))
        table.append(l)

    for k in range(ten):
        for i in range(ten):
            for j in range(ten):
                dist_mat[i][j] = min(dist_mat[i][j], dist_mat[i][k]+dist_mat[k][j])

    ans = 0
    for i in range(h):
        for t in table[i]:
            if t == -1: continue
            ans += dist_mat[t][1]


    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

A=[]
for h in range(H):
    a=map(int, input().split())
    A.append(a)
C=np.array(C)
D={-1:0}
#print(C)
#dfs
def dfs(start, now,done=[]):
    next_done=done+[start]
    #print(done)
    to_one=C[start,1]
    c=C[start]
    result=to_one
    for node, power in enumerate(c):
        
        if (node in next_done) or (start==node):
            continue
        if power<to_one:
            result=min(result,dfs(node,now+power, next_done)-now)
    #print(now,result)
    return now+result
        
for i in range(10):
    done=[]
    D[i]=dfs(i,0,[])
ans=0
for h in range(H):
    a=list(map(lambda x: D[x], A[h]))
    ans+=sum(a)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

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

converted = sum([(wf[board[h][w]][1] if board[h][w] >= 0 else 0) for w in range(W) for h in range(H)])

print(converted)

Submission status: Accepted

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

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

ans = 0
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        if A[j] != -1:
            ans += c[A[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=dict()
#cost=[[0]*10 for i in range(10)]
for i in range(h):
    line=list(map(int,input().split()))
    for l in line:
        if l==-1 or l==1:
            continue
        else:
            if l not in a:
                a[l]=1
            else:
                a[l]+=1
#print(a)

n=10

def warshall_floyd():
    #d[i][j]: iからjへの最短距離
    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])

warshall_floyd()
ans=0
for num,k in a.items():
    ans+=c[num][1]*k 
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

shortest = dijkstra(c.T,indices=1)

print(shortest[a[a>-1].reshape(-1)].sum().astype(int))

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
INF = 1<<60

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

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

    A = [list(map(int, input().split())) for _ in range(R)]
    ans = [sum([C[x][1] if x!=-1 else 0 for x in a]) for a in A]
    print(sum(ans))

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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


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

    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 Ah in A:
        for a in Ah:
            if a != -1:
                ans += C[a][1]

    print(ans)


if __name__ == '__main__':
    main()