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:
from collections import defaultdict
from itertools import product
from heapq import heappush, heappop

def floyd_warshall(V, E):
    INF = float('inf')
    N = len(V)
    dist = {u: {v: INF for v in V} for u in V}
    for v in V:
        dist[v][v] = 0
        for u, c in E[v].items(): dist[v][u] = c
    for k, i, j in product(V, repeat=3):
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist
        
H, W = map(int, input().split())
E = {i: defaultdict(int) for i in range(10)}
for i in range(10):
    C = map(int, input().split())
    for j, c in enumerate(C):
        E[i][j] = c
A = []
for _ in range(H):
    A += list(map(int, input().split()))
n_num = {i: A.count(i) for i in range(10)}
V = list(range(10))
cost = floyd_warshall(V, E)
print(sum([cost[i][1]*n_num[i] for i in range(10)]))

Submission status: Accepted

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

def pl2(L):
    for l in L:
        print(l)

def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):
    c2 = []
    while True:
        is_updated = False 
        c2 =  copy.deepcopy(c)
        for i in range(10):
            for j in range(10):
                if i != j:
                    for k in range(10):
                        if c2[i][j] > c[i][k]+c[k][j]:
                            c2[i][j] = c[i][k]+c[k][j]
                            is_updated = True
        if not is_updated:
            break
        else:
            c = copy.deepcopy(c2)

    res = 0
    for a in A:
        for c in a:
            if abs(c) != 1:
                res += c2[c][1]

    print(res)







# 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:
from scipy.sparse.csgraph import dijkstra
H,W = map(int,input().split())
g = [list(map(int,input().split())) for _ in range(10)]
d = dijkstra(g)
ans = 0
for _ in range(H):
    A = list(map(int,input().split()))
    for i in range(W):
        if A[i] != -1:
            ans += d[A[i]][1]
print(int(ans))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
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):
  arr=list(map(int,input().split()))
  for i in arr:
    if abs(i)!=1:
      ans+=d[i][1]
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse import*
a=[[abs(int(t))for t in t.split()]for t in open(0)]
print(int(sum(csgraph.dijkstra(csr_matrix(a[1:11]))[sum(a[11:],[]),1])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
a=[list(map(int,t.split()))for t in open(0)]
print(int(sum(csgraph.dijkstra(csr_matrix(a[1:11]))[[i<0 or i for i in sum(a[11:],[])],1])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
a=[list(map(int,t.split()))for t in open(0)]
print(int(sum(csgraph.dijkstra(csr_matrix(a[1:11]))[[j<0 or j for i in a[11:]for j in i],1])))

Submission status: Accepted

Solution code:
import heapq
def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n
    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
_,*a = [list(map(int,t.split())) for t in open(0)]
n = 10
edge = [[] for _ in range(n)]
for i in range(n):
    for j in range(n):
        edge[i].append((a[i][j],j))
c = [dijkstra_heap(i)[1] for i in range(n)]+[0]
print(sum(c[j] for i in a[n:] for j in i))

Submission status: Accepted

Solution code:
from scipy.sparse import*
_,*a=[list(map(int,t.split()))for t in open(0)]
print(int(sum(csgraph.dijkstra(csr_matrix(a[:10]))[[j<0 or j for i in a[10:]for j in i],1])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
_,*a=[list(map(int,t.split()))for t in open(0)]
print(int(sum(csgraph.dijkstra(csr_matrix(a[:10]))[[j for i in a[10:]for j in i if j>=0],1])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
_,*a=[list(map(int,t.split()))for t in open(0)]
c=csgraph.dijkstra(csr_matrix(a[:10]))
print(int(sum(c[j][1]for i in a[10:]for j in i if j>=0)))

Submission status: Accepted

Solution code:
from scipy.sparse import*
*a,=map(int,open(0).read().split())
c=csgraph.dijkstra(csr_matrix([a[i:i+10]for i in range(2,99,10)]))
print(int(sum(c[i][1]for i in a[102:]if i>=0)))

Submission status: Accepted

Solution code:
from scipy.sparse import*
*a,=map(int,open(0).read().split())
c=csgraph.dijkstra(csr_matrix([a[i:i+10]for i in range(2,102,10)]))
print(int(sum(c[i][1]for i in a[102:]if i>=0)))

Submission status: Accepted

Solution code:
from scipy.sparse import*
h,w,*a=map(int,open(0).read().split())
c=csgraph.dijkstra(csr_matrix([a[i*10:-~i*10]for i in range(10)]))
print(int(sum(c[i][1]for i in a[100:]if i>=0)))

Submission status: Accepted

Solution code:
from scipy.sparse import*
h,w,*a=map(int,open(0).read().split())
c=csgraph.dijkstra(csr_matrix([a[i*10:-~i*10]for i in range(10)]))
print(int(sum([c[i][1]for i in a[100:]if i>=0])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
i=lambda:list(map(int,input().split()))
h,w=i()
c=csgraph.dijkstra(csr_matrix([i()for _ in[0]*10]))
print(int(sum(c[j][1]for i in eval('i(),'*h)for j in i if j>=0)))

Submission status: Accepted

Solution code:
#import numpy as np
#from numpy import*
from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    h,w=map(int,input().split())
    grid=[list(map(int,input().split()))for i in range(10)]
    
    c=0
    grid=shortest_path(csgraph=csr_matrix(grid))
    for i in range(h):
        for j in map(int,input().split()):
            if j!=-1:
                c+=grid[j][1]
#    print(grid)
    print(int(c))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


def main():
    high, width = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(10)]
    inf = 10 ** 10
    kyori = [inf for i in range(10)]
    kyori[1] = 0

    itta = set()
    itta.add(1)
    while len(itta) < 10:
        now_kyori = inf
        ind = -1

        for ele_now in itta:
            for ele_next in range(10):
                if ele_now == ele_next or ele_next in itta:
                    continue
                length = kyori[ele_now] + data[ele_next][ele_now]
                if length < now_kyori:
                    now_kyori = length
                    ind = ele_next
        itta.add(ind)
        kyori[ind] = now_kyori


    ans = 0
    for i in range(high):
        get_data = list(map(int, input().split()))
        for ele in get_data:
            if ele == -1 or ele == 1:
                continue
            ans += kyori[ele]

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

L = [0] * 10

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

for i in range(10):
  for j in range(10):
    if j == 1:
      continue
    for k in range(10):
      if L[j] + c[k][j] < L[k]:
        L[k] = L[j] + c[k][j]

ans = 0
for l in A:
  for x in l:
    if x != -1:
      ans += L[x]

print(ans)

Submission status: Accepted

Solution code:
from heapq import *
h,w=map(int,input().split())
g=[[] for i in range(10)]
for i in range(10):
    l=list(map(int,input().split()))
    for j in range(10):
         g[i].append([l[j],j])
d={}
for i in range(10):
    q=[[0,i]]
    heapify(q)
    l=[-1 for i in range(10)]
    while l[1]==-1:
        c,t=heappop(q)
        if(l[t]==-1):
            l[t]=c
            for j in g[t]:
                C,T=j
                if(l[T]==-1):
                    heappush(q,[c+C,T])
    d[i]=l[1]           
ans=0
for i in range(h):
    l=list(map(int,input().split()))
    for j in l:
        ans+=d.get(j,0)
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
h,w=map(int,input().split())
n=10
d=[]
for i in range(n):
    d.append(list(map(int,input().split())))
a=[]
for i in range(h):
    a.append(list(map(int,input().split())))

d=floyd_warshall(d).tolist()
cnt=0
for i in range(h):
    for j in range(w):
        if a[i][j]==-1:continue
        cnt+=d[a[i][j]][1]
print(int(cnt))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
H,W = [int(i) for i in input().split()]
c=[[int(i) for i in input().split()] for _ in range(10)] 
A=[[int(i) for i in input().split()] for _ in range(H)]


dist = c
n=10
#n: 頂点数
for k,dk in enumerate(dist):
    for di in dist:
        for j in range(n):
            if di[j] > di[k]+ dk[j]:
                di[j] = di[k]+ dk[j]


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:
# coding: utf-8
# Your code here!
H,W = [int(i) for i in input().split()]
c=[[int(i) for i in input().split()] for _ in range(10)] 
A=[[int(i) for i in input().split()] for _ in range(H)]


dist = c
n=10
#n: 頂点数
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 j in range(W):
        if A[i][j] != -1:
            ans += dist[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)]

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

count=[0]*10
for i in range(H):
    l=list(map(int,input().split()))
    for j in range(10):
        count[j]+=l.count(j)
ans=0
for i in range(10):
    ans+=count[i]*c[i][1]

print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

MAT=[list(map(int, input().split())) for i in range(10)]
INM=[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):
            MAT[i][j] = min(MAT[i][j], MAT[i][k] + MAT[k][j])
            MAT[j][i] = min(MAT[j][i], MAT[j][k] + MAT[k][i])

res = 0
for i in range(H):
    for j in range(W):
        if INM[i][j] != -1:
            res += MAT[INM[i][j]][1]

print(res)

Submission status: Accepted

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

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

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

#dijkstra
#you need to prepare e_list = [[orient,dist]]

import heapq

d_list = []
N=10
for i in range(10):
    vi = i
    min_d_list = [10**27 for i in range(N)]
    min_d_list[vi] = 0
    prev_list = [-1 for i in range(N)]
    q = []
    for i in range(N):
        heapq.heappush(q,[min_d_list[i],i])

    while len(q)>0:
        d,v = heapq.heappop(q)
        for e in e_list[v]:
            v1,d1=e
            if min_d_list[v1]>d+d1:
                min_d_list[v1]=d+d1
                prev_list[v1]=v
                heapq.heappush(q,[d+d1,v1])
    d_list.append(min_d_list)
score=0
for i in range(H):
    for j in range(W):
        if A[i][j]!=-1:
            score+=d_list[A[i][j]][1]

print(score)

Submission status: Accepted

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

ct=0
for i in range(h):
  for j in range(w):
    if a[i][j]>=0:
      ct+=ansL[a[i][j]]
print(ct)

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


main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
inf = 10**8
d = [[inf for _ in range(10)] for _ in range(10)]
c = []
for i in range(10):
    c = list(map(int, input().split()))
    for j in range(10):
        d[i][j] = c[j]


# 各数字から１への最小コストを求める
for k in range(10):
    for i in range(10):
        for j in range(10):
            d[i][j]= min(d[i][j], d[i][k] + d[k][j])

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 += d[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)]
for i in range(10):
    for j in range(10):
        for k in range(10):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])
for i in range(10):
    for j in range(10):
        for k in range(10):
            c[i][j]=min(c[i][j],c[i][9-k]+c[9-k][j])
for i in range(10):
    for j in range(10):
        for k in range(10):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])
l=[]
for i in range(h):
    l.extend(list(map(int,input().split())))
x=0
for i in range(10):
    x+=c[i][1]*l.count(i)
print(x)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
cs =[list(map(int, input().split())) for _ in range(10)]
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(10):
        for i in range(10):
            for j in range(10):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
cs = warshall_floyd(cs)
As = [list(map(int, input().split())) for _ in range(H)]
ans = 0
for A in As:
    for a in A:
        if a != -1:
            ans += cs[a][1]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import heapq
from collections import Counter
INF = float("inf")

# 無向グラフを仮定する。


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])

        pass


def shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):
    g = Graph(10)
    # 向きを逆向きにuとｒ
    for i in range(10):
        for j in range(10):
            g.add_edge([j, i, c[i][j]])

    c = Counter()
    for a in A:
        c.update(a)

    # 逆向きにとった効果として、１から他の数字への距離を求めれば良い
    dist, prev = shortestPath(g, 1)
    # print(dist)
    # print(c)
    ans = 0
    for key in c:
        if key == 1 or key == -1:
            continue
        ans += dist[key]*c[key]

    print(ans)
    return


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:
#coding:utf-8
from Queue import PriorityQueue
H,W=map(int,raw_input().split())
c=[]
for i in range(10):
    c.append(map(int,raw_input().split()))

A=[]
for i in range(H):
    A.append(map(int,raw_input().split()))
cost=[-1]*10
cost[1]=0
pq=PriorityQueue()
for i in range(0,10): 
    if i!=1:pq.put((c[i][1],i))
while not pq.empty():
    co,po=pq.get()
    if cost[po]!=-1:continue
    cost[po]=co
    for i in range(0,10):
        if cost[i]==-1:
            pq.put((c[i][po]+co, i))

ans=0
for L in A:
    for l in L:
        if l!=-1:ans+=cost[l]
print(ans)

Submission status: Accepted

Solution code:
def sol():
    h,w=map(int,input().split())
    c=[list(map(int,input().split())) for i in range(10)]
    a=[list(map(int,input().split())) for i in range(h)]
    for k in range(10):
        for i in range(10):
            for j in range(10):
                #if (c[i][k]!=0 and c[k][j]!=0): c[i][j]=min(c[i][j],c[i][k]+c[k][j])
                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: pass
            else: ans+=c[a[i][j]][1]
    print(ans)

if __name__=="__main__":
    sol()

Submission status: Accepted

Solution code:
from itertools import product

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

# 整数 i を 0 に書き換えるのに必要な魔力の最小量を求める
G = [{} for _ in range(10)]
for i, j in product(range(10), repeat=2):
    G[i][j] = c[i][j]
INF = 10**10


def warshall_floyd(G):
    dp = [
        [
            0 if i == j else
            G[i][j] if j in G[i] else
            INF
            for j in range(len(G))
        ]
        for i in range(len(G))
    ]
    for k in range(len(G)):
        for i in range(len(G)):
            for j in range(len(G)):
                dp[i][j] = (
                    dp[i][j] if dp[i][k] == INF or dp[k][j] == INF else
                    min(dp[i][j], dp[i][k] + dp[k][j])
                )
    return dp


dp = warshall_floyd(G)
# すべての数字について、dp を用いて解を求める
ans = sum(
    dp[x][1]
    for a in A
    for x in a
    if x >= 0
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
def sol():
    h,w=map(int,input().split())
    c=[]
    for i in range(10):
        l=[int(i) for i in input().split()]
        c.append(l)
    a=[]
    for i in range(h):
        l=[int(i) for i in input().split()]
        a.append(l)
    p=[0]*10
    for i in range(10):
        if i==1: continue
        d=[1003]*10
        d[i]=0
        q=set([i])
        while 1:
            if len(q)==0: break
            x=q.pop()
            for j in range(10):
                if i==j: continue
                if (d[j]>d[x]+c[x][j]):
                    d[j]=d[x]+c[x][j]
                    q.add(j)
        p[i]=d[1]
    ans=0
    for i in range(h):
        for j in range(w):
            if a[i][j]==-1: pass
            else: ans+=p[a[i][j]]
    print(ans)

if __name__=="__main__":
    sol()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
c=[]
for i in range(10):
    l=[int(i) for i in input().split()]
    c.append(l)
a=[]
for i in range(h):
    l=[int(i) for i in input().split()]
    a.append(l)
p=[0]*10
for i in range(10):
    if i==1: continue
    d=[1003]*10
    d[i]=0
    q=set([i])
    while 1:
        if len(q)==0: break
        x=q.pop()
        for j in range(10):
            if i==j: continue
            if (d[j]>d[x]+c[x][j]):
                d[j]=d[x]+c[x][j]
                q.add(j)
    p[i]=d[1]
ans=0
for i in range(h):
    for j in range(w):
        if a[i][j]==-1: pass
        else: ans+=p[a[i][j]]
print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd(c):
    d = {}

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

def answer(h, w, c, a):
    ans = 0
    d = warshall_floyd(c)
    count = []

    for i in range(10):
        count.append(0)
    
    for i in range(h):
        for j in range(w):
            if a[i][j] != -1:
                count[a[i][j]] += 1

    for i in range(10):
        ans += d[i, 1] * count[i]

    return ans


[h, w] = list(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())))

print(str(answer(h, w, c, a)))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
h,w=map(int,input().split())
table=[[0]*10 for i in range(10)]
for i in range(10):
  C=[int(i) for i in input().split()]
  for j in range(10):
    table[i][j]=C[j]
d=floyd_warshall(csgraph=table, directed=True, return_predecessors=False)
ans=0
for i in range(h):
  A=[int(i) for i in input().split()]
  for a in A:
    if a!=-1:
      ans+=int(d[a][1])
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int, input().split())
c=[list(map(int,input().split())) for i in range(10)]
A=[list(map(int,input().split())) for i in range(H)]
def dfs(n,tcost,depth):
    for i in range(10):
        if cost[i]>tcost+c[i][n]:
            cost[i]=tcost+c[i][n]
            if depth<10:
                dfs(i,cost[i],depth+1)
cost=[10**4]*11
cost[1]=0
cost[-1]=0
dfs(1,0,0)
ans=0
for h in range(H):
    for w in range(W):
        ans+=cost[A[h][w]]
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)]

from scipy.sparse.csgraph import floyd_warshall
cost=floyd_warshall(c)

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

print(total)

Submission status: Accepted

Solution code:
H,W = [ int(it) for it in input().split() ]
li = [ [ int(it) for it in input().split() ] for i in range(10) ]

from copy import deepcopy

for _ in range(19):
  li2 = deepcopy(li)
  for i in range(10):
    for j in range(10):
      for k in range(10):
        li2[i][j] = min( li2[i][j] , li[i][k]+li[k][j] )
  li = li2

gr = []
for i in range(H):
  gr.extend([ int(it) for it in input().split() ])
  
import collections  as cols
ccc = cols.Counter(gr)
cost = 0
for k,v in ccc.items():
  if (k!=-1):
    cost += v*li[k][1]
print ( cost )

Submission status: Accepted

Solution code:
import sys

import numpy as np
from scipy.sparse.csgraph import dijkstra

sys.setrecursionlimit(10000)
INF = float('inf')

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

mp = dijkstra(C, directed=True)[:, 1]
ans = 0
for n in range(10):
    ans += mp[n] * np.sum(A == n)
print(int(round(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)]
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 = 0
for i in range(h):
    for j in range(w):
        if a[i][j]==-1:
            continue
        cost += c[a[i][j]][1]
print(cost)

Submission status: Accepted

Solution code:
from functools import reduce
import math
import copy

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    H, W = (int(_) for _ in input().split())
    c = []
    for i in range(10):
        c.append(list(int(_) for _ in input().split()))
    A = []
    for i in range(H):
        A.append(list(int(_) for _ in input().split()))

    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] != -1:
                ans += d[A[i][j]][1]
    print(ans)
    
if __name__ == '__main__':
    main()

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)]
memo = {}
def dfs(nv,vl,cost):
    if nv==1:
        return cost
    if nv in memo.keys():
        return cost+memo[nv]
    vl_ = vl.copy()
    vl_.append(nv)
    ret = []
    for i in range(10):
        if not i in vl_:
            ret.append(dfs(i,vl_,cost+c[nv][i]))
    return min(ret)
cost = []
for i in range(10):
    memo[i] = dfs(i,[],0)
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j]!=-1:
            ans += memo[a[i][j]]
print(ans)