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

H,W=map(int,input().split())
dp=[[float("inf") for _ in range(10)] for _ in range(10)]
cnt = defaultdict(lambda:0)
ans=0

for i in range(10):
    tmp=tuple(map(int,input().split()))
    for k in range(10):
        dp[i][k]=tmp[k]
    dp[i][i]=0

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

for _ in range(H):
    cn=list(map(int,input().split()))
    for x in cn:
            cnt[x]+=1

for n in range(10):
    ans+=cnt[n]*dp[n][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)]

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

Submission status: Accepted

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

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 A[i]:
        if j != -1:
            ans += c[j][1]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
import numpy as np
# import numpy as np
# 答えの提出の時にi+1とj+1は忘れないように
h, w = map(int, input().split())
cost = [[-1 for i in range(10)] for j in range(10)]

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

cost = np.array(cost).T

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : vからuへのコスト(逆にした)
    d = [float("inf")] * (n+1)
    used = [False] * n
    d[s] = 0
    num = [0]*n # 視点sから各頂点への最短経路の経路数を保存するリスト
    num[s] = 1 # 辺の重みが0のやつがあったらここ使えないな

    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True

        for j in range(n):
            if d[j] > d[v]+cost[v][j]: # vを使った場合と使わない場合の最短値で比較
                d[j] = d[v]+cost[v][j]

    return d

d = dijkstra(1,10,100,cost)
d[-1] = 0

ans = 0
for _ in range(h):
    for number in list( map(int, input().split())):
        ans += d[number]

print(ans)

Submission status: Accepted

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

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

def wf(table):
    from itertools import product
    for k, i, j in product(range(len(table)), repeat=3):
        table[i][j] = min(table[i][j], table[i][k] + table[k][j])

    return table

table = wf(table)

ans = 0
for _ in range(h):
    for i in map(int, input().split()):
        if i != -1:
            ans += table[i][1]

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(10)]
A = [list(map(int, input().split())) for _ in range(h)]

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

d = warshall_floyd(d)
ans = 0
for i in range(h):
    for j in range(w):
        if A[i][j] not in [-1, 1]:
            ans += d[A[i][j]][1]


print(ans)

Submission status: Accepted

Solution code:
#全点対最短路
def wf(d,v):
    for k in range(v):
        for i in range(v):
            for j in range(v):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    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)]

l = [0 for _ in range(10)]
for i in a:
    for j in i:
        if j != -1:
            l[j]+=1

s = [i[1] for i in wf(c,10)]

ans = 0
for i in range(len(l)):
    if i != 1:
        ans+=s[i] * l[i]

print(ans)

Submission status: Accepted

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

dp = [-1] * 10
for i in range(10):
    dp[i] = list(map(int,input().split()))

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

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

ans = 0
for _ in range(h):
    a = list(map(int,input().split()))
    for i in range(w):
        if a[i] == 1 or a[i] == -1:
            pass

        else:
            ans += dp[a[i]][1]

print(ans)

Submission status: Accepted

Solution code:
def calc_mp(C, d):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if k == 0:
                    d[i][j][k] = min(C[i][j], C[i][k] + C[k][j])
                else:
                    d[i][j][k] = min(d[i][j][k-1], d[i][k][k-1] + d[k][j][k-1])

def main():
    H, W = map(int, input().split())
    C = [0]*10
    for i in range(10):
        C[i] = list(map(int, input().split()))
    A = [0]*H
    for i in range(H):
        A[i] = list(map(int, input().split()))
    # print(H, W, C, A)

    d = [[[0 for i in range(10)] for i in range(10)] for i in range(10)]
    calc_mp(C, d)

    # print(d)
    ans = 0
    for h in range(H):
        for w in range(W):
            a = A[h][w]
            if a != -1 and a != 1:
                ans += d[a][1][9]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def calc_mp(C, candidates, n, ans):
    for i in range(len(candidates)):
        candidates2 = [c for c in candidates]
        c = candidates[i]
        del candidates2[i]
        a = C[n][c]
        if c != 1:
            a += calc_mp(C, candidates2, c, ans)
        ans = min(a, ans)
    return ans

def main():
    H, W = map(int, input().split())
    C = [0]*10
    for i in range(10):
        C[i] = list(map(int, input().split()))
    A = [0]*H
    for i in range(H):
        A[i] = list(map(int, input().split()))
    # print(H, W, C, A)

    MPs = [0]*10
    for i in range(10):
        if i != 1:
            candidates = [j for j in range(10)]
            del(candidates[i])
            MPs[i] = calc_mp(C, candidates, i, 1000)
    # print(MPs)
    ans = 0
    for h in range(H):
        for w in range(W):
            a = A[h][w]
            if a != -1:
                ans += MPs[a]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
INF=float('inf')
dp=[[INF]*10 for _ in range(10)]
for i in range(10):
  a=list(map(int,input().split()))
  for j in range(10):
    dp[i][j]=a[j]
for k in range(10):
  for i in range(10):
    for j in range(10):
      dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
cnt=0
for i in range(H):
  a=list(map(int,input().split()))
  for j in range(W):
    if a[j]==-1 or a[j]==1:
      pass
    else:
      cnt+=dp[a[j]][1]
print(cnt)

Submission status: Accepted

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


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


a = [[0] * w for _ in range(h)]
for i in range(h):
    a[i] = list(map(int, input().split()))


arr = []
for i in range(h):
    for j in range(w):
        if a[i][j] == -1 or a[i][j] == 1:
            pass
        else:
            arr.append(a[i][j])


# 0 - 9それぞれを1に書き換える最小コストを計算
# arrに格納された数を全て最小コストで処理する
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(len(arr)):
    cost += c[arr[i]][1]
print(cost)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc079/tasks/abc079_d
# D - Wall

# import pprint

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

for i in range(10):
    cost_list = list(map(int, input().split()))
    costs.append(cost_list)
    # for j, cost in enumerate(cost_list):
    #     costs.append({"i": i, "j": j, "c": cost})

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

# warshall_floyd
for k in range(10):
    for i in range(10):
        for j in range(10):
            costs[i][j] = costs[i][j] if costs[i][j] < costs[i][k] + costs[k][j] else costs[i][k] + costs[k][j]

# pprint.pprint(costs)
# pprint.pprint(wall)

ans = 0 
for i, line in enumerate(wall):
    for j, cell in enumerate(line):
        if cell == -1:
            continue
        ans = ans + costs[cell][1]
print(str(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 i in range(10)]
A = [list(map(int,input().split())) for i in range(H)]

def dfs(i, j) :
    magi = c[i][1] + j
    for k in range(10) :
        if visited[k] == 0 and c[i][k] < c[i][1] :
            visited[k] = 1
            magi = min(magi, dfs(k, c[i][k] + j))
            visited[k] = 0
    return magi

ans = [10**5 for _ in range(10)]
for i in range(10) :
    visited = [0 for _ in range(10)]
    visited[i] = 1
    ans[i] = dfs(i, 0)

ans2 = 0
for ai in A :
    for aii in ai :
        if aii == -1 :
            continue
        else :
            ans2 += ans[aii]

print(ans2)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
C = []
for _ in range(10):
  List = list(map(int,input().split()))
  C.append(List)
Wall = []
for _ in range(H):
  List = list(map(int,input().split()))
  Wall.append(List)
for k in range(10):
  for i in range(10):
    for j in range(10):
      if i != j:
        C[i][j] = min(C[i][j],C[i][k]+C[k][j])
      else:
        C[i][j] = 0
Answer = 0
for line in Wall:
  for item in line:
    if item!= -1:
      Answer += C[item][1]
print(Answer)

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):
            d = C[i][k] + C[k][j]
            if d < C[i][j]:
                C[i][j] = d

ans = 0
cost = [C[i][1] for i in range(10)]

for _ in range(H):
    for n in map(int, input().split()):
        if n == -1:
            continue
        ans += cost[n]

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
G=[[0]*10 for i in range(10)]
for i in range(10):
  G[i]=list(map(int,input().split()))
A=[1,2,6,24,120,720,5040,40320]
B=[i for i in range(10)]
E=[0]*10
for i in range(10):
  if i==1:
    continue
  E[i]=10**10
  for j in range(362880):
    C=B[0:11]
    D=[i]
    C.remove(i)
    for k in range(8):
      a=j//A[-1-k]
      j=j-A[-1-k]*a
      b=C.pop(a)
      D.append(b)
      if b==1:
        break
    D.append(C[0])
    c=0
    for j in range(9):
      if D[j]==1:
        break
      c=c+G[D[j]][D[j+1]]
    if c<E[i]:
      E[i]=c
F=[0]*11
GG=[[0]*w for i in range(h)]
for i in range(h):
  GG[i]=list(map(int,input().split()))
  for j in range(w):
    F[GG[i][j]]=F[GG[i][j]]+1
ans=0
for i in range(10):
  ans=ans+E[i]*F[i]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

h , w = map(int , input().split())
c = [[] for _ in range(10)]
a = [[] for _ in range(h)]
b = Counter()
for i in range(10):
    c[i] = list(map(int,input().split()))
    
for i in range(h):
    a[i] = list(map(int,input().split()))
    b += Counter(a[i])
    
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(10):
    ans += (c[i][1] * b[i] )
    
print(ans)

Submission status: Accepted

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

def Warshall_Floyd(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
h, w = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
n = 10
Warshall_Floyd(c)

A =[list(map(int, input().split())) for _ in range(h)]
S = []
S_append = S.append
for a in A:
    for i in a:
      if i != -1 and i != 1:
        S_append(i)
ans = 0
for s in S:
  ans += c[s][1]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = lambda: sys.stdin.readline().rstrip()

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

c_list = []

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


for k in range(10):
    for i in range(10):
        for j in range(10):
            c_list[i][j] = min(c_list[i][j], c_list[i][k] + c_list[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 += c_list[A[j]][1]

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
c = [[int(i) for i in input().split()] for _ in range(10)]
a = [[int(i) for i in input().split()] for _ in range(h)]
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 a_ in a:
    for ai in a_:
        if ai == 1 or ai == -1: continue
        else: ans += c[ai][1]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H, W = map(int, raw_input().split())
c = []

for i in range(10):
    ci = map(int, raw_input().split())
    c.append(ci)

A = []

for i in range(H):
    ai = map(int, raw_input().split())
    A.append(ai)


dp = [[0]*10 for _ in range(10)]

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

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


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

print ans

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    h,w = LI()
    d = LIR(10)
    for k in range(10):
        for i in range(10):
            for j in range(10):
                nd = d[i][k]+d[k][j]
                if nd < d[i][j]:
                    d[i][j] = nd
    a = LIR(h)
    ans = 0
    for i in a:
        for j in i:
            if j < 0:
                continue
            ans += d[j][1]
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

m = [list(map(int, input().rstrip().split())) for _ in range(10)]

def dfs(i, v):
    if i == 1:
        return v
        
    min_v = int(1e9)
    for j in range(10):
        if f[j] == False:
            f[j] = True
            min_v = min(min_v, v + dfs(j, m[i][j]))
            f[j] = False
            
    return min_v
    
min_vs = [-1] * 10
for i in range(10):
    f = [False] * 10
    f[i] = True
    min_vs[i] = dfs(i, 0)
min_vs += [0]
    
v = 0
for _ in range(H):
    v += sum(list(map(lambda x: min_vs[int(x)], input().rstrip().split()))) 
print(v)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

def disktra(g,s):
    n=len(g)
    dist = [inf]*n
    dist[s] = 0
    hq=[]
    heapq.heappush(hq,(dist[s],s))
    while hq:
        cost,u =heapq.heappop(hq)
        if dist[u] < cost:
            continue
        for v,c in g[u]:
            if dist[v] <= dist[u] +c:
                continue
            dist[v] = dist[u] + c
            heapq.heappush(hq,(dist[v],v))
    return dist

h,w = map(int,input().split())
C = [list(map(int,input().split())) for i in range(10)]
G = [[] for i in range(10)]
for i,ci in enumerate(C):
  for j,vj in enumerate(ci):
    G[j].append((i,vj))
dist = disktra(G,1)
for i in range(h):
  for number in map(int,input().split()):
    if number == -1: continue
    ans += dist[number]
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
c = []
a = []

for _ in range(10):
    c.append(list(map(int, input().split())))

for _ in range(h):
    a.append(list(map(int, input().split())))

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]  # 1までの最短コスト

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
costs = []
wall = []

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

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

total_cost = 0

for i in range(H):
  for j in range(W):
    n = wall[i][j]
    if n == -1:
      continue
    total_cost += costs[n][1]
    
print(total_cost)

Submission status: Accepted

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

  kakutei_num = 1
  while kakutei_num != 10:
    min_num = 1000000
    index = -1
    for j in range(10):
      if not kakutei[j] and min_num > arr[j]:
        min_num = min(min_num, arr[j])
        index = j
      
    kakutei[index] = True
    kakutei_num += 1
    for j in range(10):
      c[i][j] = min(c[i][j], c[i][index] + c[index][j])
      
ans = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == -1:
      continue
    
    n = a[i][j]
    ans += c[n][1]
'''    
for i in range(len(c)):
  print(c[i])
'''
print(ans)

Submission status: Accepted

Solution code:
def main():
    height, width = map(int, input().split())
    change_cost = [list(map(int, input().split())) for _ in range(10)]
    grid = [list(map(int, input().split())) for _ in range(height)]
    for k in range(10):
        for i in range(10):
            for j in range(10):
                change_cost[i][j] = min(change_cost[i][j], change_cost[i][k] + change_cost[k][j])
    answer = 0
    for g in grid:
        for n in g:
            if abs(n) != 1:
                answer += change_cost[n][1]
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import shortest_path
import numpy as np
H,W = [int(i) for i in input().split()]
c = [0] * 10
for i in range(10):
    c[i] = [int(j) for j in input().split()]
c = np.array(c)
path = shortest_path(c,'D')
A = [0] * H
for i in range(H):
    A[i] = [int(j) for j in input().split()]
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == 1 or A[i][j] == -1:
            continue
        ans += path[A[i][j]][1]
print(int(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)]

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

G = np.array(c)
dist = floyd_warshall(G)

#print(dist)
ans = 0
for i in range(h):
    for j in range(w):
        ai = a[i][j]
        if ai == -1:
            continue
        ans += dist[ai][1]
print(int(ans))

Submission status: Accepted

Solution code:
#079_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)]

def warshall_floyd(d, v):
    for k in range(v):
        for i in range(v):
            for j in range(v):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
            
warshall_floyd(c, 10)
res = 0
for i in range(h):
    for j in range(w):
        if a[i][j] != -1:
            res += c[a[i][j]][1]
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def readlines(n):
    for _ in range(n):
        yield list(map(int, input().split()))

def main():
    h, w = map(int, input().split())

    C = list(readlines(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])

    for line in readlines(h):
        yield sum(C[c][1] for c in line if c != -1) 


print(sum(main()))


main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
from itertools import chain

def readlines(n):
    for _ in range(n):
        yield map(int, input().split())

def main():
    h, w = map(int, input().split())

    C = [[int(c) for c in 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])

    counter = Counter(chain(*readlines(h)))

    for i in range(10):
        yield C[i][1] * counter[i]


print(sum(main()))


main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
from itertools import chain

def readlines(n):
    for _ in range(n):
        yield map(int, input().split())

def main():
    h, w = map(int, input().split())

    C = list(map(list, readlines(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])

    counter = Counter(chain(*readlines(h)))

    for i in range(10):
        yield C[i][1] * counter[i]


print(sum(main()))


main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
from itertools import chain

def readlines(n):
    for _ in range(n):
        yield list(map(int, input().split()))

def main():
    h, w = map(int, input().split())

    C = list(readlines(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])

    c = Counter(chain(*readlines(h)))

    for i in range(10):
        yield C[i][1] * c[i]


print(sum(main()))


main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

N,M = m()

po = [l() for i in range(10)]

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


num = [0 for i in range(10)]

co = 0

for i in range(N):
    aaa = l()
    for j in aaa:
        if j != -1:
            num[j] += 1

for i in range(10):
    if i != 1:
        co += po[i][1] * num[i]
print(co)

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)]
dp = [[10 ** 4 for _ in range(10)] 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])
b = [0] + [c[i][1] for i in range(10)]
ans = 0
for i in a:
    for j in i:
        ans += b[j + 1]
print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

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


def main():
    H, W = MAP()
    C = [LIST() for _ in range(10)]
    A = [LIST() for _ in range(H)]

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
C = []
for i in range(10):
    tmp = LIST()
    C.append(tmp)
A = []
for i in range(H):
    tmp = LIST()
    A.append(tmp)
    

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

C = warshall_floyd(C, 10)

ans = 0

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