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: Runtime Error

Solution code:
import heapq

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

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

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

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

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

Submission status: Runtime Error

Solution code:
import heqpq

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

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

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

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

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

Submission status: Runtime Error

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

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])
#print(c)

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

Submission status: Runtime Error

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


inf = 10**9+7

point = [inf] * 10


for i in range(10):
    tmp = 0
    for j in range(10):
        tmp += C[i][j]
        point[i] = min(point[i],tmp+C[j][1])
        
ans = 0
for i in range(H):
    for j in range(W):
        if H[i][j] != -1:
            ans += point[H[i][j]]
            
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
distance=[]
for _ in range(10):
   distance.append(list(map(int,input().split())))

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

ans=0
for _ in range(h):
   A=list(map(int,input().split()))
   for a in A:
      if a!=-1:
         ans.append(distance[a][0])
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    for i in range(2):
        if s[i] == s[i + 1] == s[i + 2]:
            print("Yes")
            return
    print("No")
    return

#B
def B():
    return

#C
def C():
    abcd = list(map(int, S()))
    op = itertools.product(range(2), repeat=3)
    for opx in op:
        ans = abcd[0]
        for num, opi in enumerate(opx):
            if opi:
                ans += abcd[num + 1]
            else:
                ans -= abcd[num + 1]
        if ans == 7:
            print(abcd[0],end="")
            for num, opi in enumerate(opx):
                print(["-", "+"][opi] + str(abcd[num + 1]), end="")
            print("=7")
            return
    return

#D
def D():
    h, w = LI()
    edg = LIR(9)
    for k in range(9):
        for x in range(9):
            for y in range(9):
                edg[x][y] = min(edg[x][k] + edg[k][y], edg[x][y])
    a = LIR(h)
    ans = 0
    for y in range(h):
        for x in range(w):
            if a[y][x] == -1:
                continue
            ans += edg[a[y][x]][1]
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    for i in range(2):
        if s[i] == s[i + 1] == s[i + 2]:
            print("Yes")
            return
    print("No")
    return

#B
def B():
    return

#C
def C():
    abcd = list(map(int, S()))
    op = itertools.product(range(2), repeat=3)
    for opx in op:
        ans = abcd[0]
        for num, opi in enumerate(opx):
            if opi:
                ans += abcd[num + 1]
            else:
                ans -= abcd[num + 1]
        if ans == 7:
            print(abcd[0],end="")
            for num, opi in enumerate(opx):
                print(["-", "+"][opi] + str(abcd[num + 1]), end="")
            print("=7")
            return
    return

#D
def D():
    h, w = LI()
    edg = LIR(9)
    for k in range(9):
        for x in range(9):
            for y in range(9):
                edg[x][y] = min(edg[x][k] + edg[k[y]], edg[x][y])
    a = LIR(h)
    ans = 0
    for y in range(h):
        for x in range(w):
            if a[y][x] == -1:
                continue
            ans += edg[a[y][x]][1]
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
d = []
for i in range(10):
    d.append(map(int, input().split()))
a = []
for i in range(h):
    a.append(map(int, input().split()))
for k in range(10):
    for i in range(10):
        for j in range(10):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]

#for k in range(0, 10):
#    print(c[k])
#for k in range(0, 10):
#    print(d[k])
#print(d[8][1])

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

Submission status: Runtime Error

Solution code:
h, w = input().split()
d = []
for i in range(10):
    d.append(map(int, input().split()))
a = []
for i in range(h):
    a.append(map(int, input().split()))
for k in range(10):
    for i in range(10):
        for j in range(10):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]

#for k in range(0, 10):
#    print(c[k])
#for k in range(0, 10):
#    print(d[k])
#print(d[8][1])

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

Submission status: Runtime Error

Solution code:
x = input().split()
#x = "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".split()
#x = "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".split()
h = int(x[0])
w = int(x[1])
d = []
for i in range(10):
    d.append(
        list(map(int, x[2 + i * 10 : 2 + i * 10 + 10]))
    )
a = []
for i in range(h):
    a.append(
        list(map(int, x[102 + i * w: 102 + i * w + w]))
    )
#d = [[0] * 10] * 10
for k in range(10):
    for i in range(10):
        for j in range(10):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]

#for k in range(0, 10):
#    print(c[k])
#for k in range(0, 10):
#    print(d[k])
#print(d[8][1])

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

Submission status: Runtime Error

Solution code:
import networkx as nx
G=nx.DiGraph()
G.add_nodes_from([i for i in range(0,10)])
h,w=map(int,input().split())
for i in range(10):
    l=list(map(int,input().split()))
    for j in range(10):
         G.add_edge(i,j,weight=l[j])
d={}
for i in range(10):
    l,p=nx.multi_source_dijkstra(G,[i],target=1)
    d[i]=l
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: Runtime Error

Solution code:
# ABC 079 D


class WarshallFloyd:

    def __init__(self, adj):
        """
        ワーシャル・フロイド法によって全頂点間の最短距離を O(|V|^3) で計算する。

        :param adj: 隣接行列 adj[i][j] でi番目の頂点からj番目の頂点へのコストを示す パスがなければINF
        """
        self._dist = adj  # 各頂点間の最短距離 初期値として隣接行列をそのまま用い、[i, i]要素を0に初期化する
        for i in range(len(adj)):
            self._dist[i][i] = 0

        self._solve()

    def _solve(self):
        v_len = len(self._adj)
        for i in range(v_len):  # 経由する頂点
            for j in range(v_len):  # 開始頂点
                for k in range(v_len):  # 終端
                    self._dist[j][k] = min(self._dist[j][k], self._dist[j][i] + self._dist[i][k])

    def distance(self, start, goal):
        return self._dist[start][goal]

    def path(self, start, goal):
        pass


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

wf = WarshallFloyd(C)

cost = 0
for ln in A:
    for a in ln:
        if a == -1:
            continue
        cost += wf.distance(a, 1)
print(cost)

Submission status: Runtime Error

Solution code:
# ABC 079 D


class WarshallFloyd(object):

    def __init__(self, adj):
        """
        ワーシャル・フロイド法によって全頂点間の最短距離を O(|V|^3) で計算する。

        :param adj: 隣接行列 adj[i][j] でi番目の頂点からj番目の頂点へのコストを示す パスがなければINF
        """
        self._dist = adj  # 各頂点間の最短距離 初期値として隣接行列をそのまま用い、[i, i]要素を0に初期化する
        for i in range(len(adj)):
            self._dist[i][i] = 0

        self._solve()

    def _solve(self):
        v_len = len(self._adj)
        for i in range(v_len):  # 経由する頂点
            for j in range(v_len):  # 開始頂点
                for k in range(v_len):  # 終端
                    self._dist[j][k] = min(self._dist[j][k], self._dist[j][i] + self._dist[i][k])

    def distance(self, start, goal):
        return self._dist[start][goal]

    def path(self, start, goal):
        pass


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

wf = WarshallFloyd(C)

cost = 0
for ln in A:
    for a in ln:
        if a == -1:
            continue
        cost += wf.distance(a, 1)
print(cost)

Submission status: Runtime Error

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[k][j]!=0): 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: Runtime Error

Solution code:
def son():
    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: Runtime Error

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)
A[A == -1] = 1

mp = dijkstra(C, directed=True)[:, 1]
nums, counts = np.unique(A, return_counts=True)
print(int((mp[nums] * counts).sum()))

Submission status: Runtime Error

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

nuns = 10

for k in range(nums):
  for i in range(nums):
    for j in range(nums):
      cost[i][j] = min(cost[i][j],
                       cost[i][k] + cost[k][j])

ans = 0
for wi in wall:
  for wij in wi:
    ans += 0 if wij == 0 else cost[wij][1]
    
print(ans)

Submission status: Runtime Error

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

nuns = 10

for k in range(nums):
  for i in range(nums):
    for j in range(nums):
      cost[i][j] = min(cost[i][j],
                       cost[i][k] + cost[k][j])

ans = 0
for wi in wall:
  for wij in wi:
    ans += 0 if wij == 0 else cost[wij][1]
    
print(h,w = map(int, input().split())
cost = [list(map(int, input().split())) for _ in range(10)]
wall = [list(map(int, input().split())) for _ in range(h)]

nuns = 10

for k in range(nums):
  for i in range(nums):
    for j in range(nums):
      cost[i][j] = min(cost[i][j],
                       cost[i][k] + cost[k][j])

ans = 0
for wi in wall:
  for wij in wi:
    ans += 0 if wij == 0 else cost[wij][1]
    
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
inf = float("inf")
dp = [[inf]*100 for _ in [0]*100]
for i in range(N):dp[i][i] = 0
d = [list(map(int, input().split())) for i in range(10)]
m = [list(map(int, input().split())) for i in range(N)]
ans = 0
 
for i in range(10):
    for j in range(10):
        dp[i][j] = d[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])
c=0

print(c)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
inf = float("inf")
dp = [[inf]*100 for _ in [0]*100]
for i in range(N):dp[i][i] = 0
d = [list(map(int, input().split())) for i in range(10)]
m = [list(map(int, input().split())) for i in range(N)]
ans = 0
 
for i in range(10):
    for j in range(10):
        dp[i][j] = d[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])
c=0
for i in range(N):
    for j in range(M):
        if m[i][j] != 1 :
            if m[i][j] != -1 :
                c+=dp[m[i][j]][1]
print(c)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
inf = float("inf")
dp = [[inf]*10 for _ in [0]*10]
for i in range(N):dp[i][i] = 0
d = [list(map(int, input().split())) for i in range(10)]
m = [list(map(int, input().split())) for i in range(N)]
ans = 0
 
for i in range(10):
    for j in range(10):
        dp[i][j] = d[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])
c=0
for i in range(N):
    for j in range(M):
        if m[i][j] != 1 :
            if m[i][j] != -1 :
                c+=dp[m[i][j]][1]
print(c)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
inf = float("inf")
dp = [[inf]*10 for _ in [0]*10]
for i in range(N):dp[i][i] = 0
d = [list(map(int, input().split())) for i in range(10)]
m = [list(map(int, input().split())) for i in range(N)]
ans = 0
 
for i in range(10):
    for j in range(10):
        dp[i][j] = d[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])
c=0
for i in range(N):
    for j in range(M):
        if m[i][j] != 1 and m[i][j] != -1 :
            c+=dp[m[i][j]][1]
print(c)

Submission status: Runtime Error

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

def w_f():
    cost=[]
    for i in range(10):
        cost.append(list(map(int,input().strip().split(' '))))

    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])
    rerurn cost
    
d=w_f()
ans=0
for i in range(H):
    a=list(map(int,input().strip().split(' ')))
    for j in a:
        if j!=-1:
            ans+=cost[j][1]
print(ans)

Submission status: Runtime Error

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

V=10
E=45
inf=10**9

def w_f():
    cost=[]
    for i in range(10):
        cost.append(list(map(int,input().strip().split(' '))))

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


d=w_f()

ans=0
for i in range(H):
    a=list(map(int,input().strip().split(' ')))
    for j in a:
        if j!==-1:
            ans+=d[j][1]

print(ans)

Submission status: Runtime Error

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

V=10
E=45
inf=10**9

def w_f():
    for i in range(10):
        c=list(map(int,input().strip().split(' ')))
        for j in range(10):
            cost[i][j]=c[j]

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


d=w_f()

ans=0
for i in range(H):
    a=list(map(int,input().strip().split(' ')))
    for j in range(W):
        if a[j]!=-1:
            ans+=d[a[j]][1]

print(ans)

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
C = []
A = []
for i in range(10) :
    C.append(list(map(int,inpput().split())))
for i in range(H) :
    A.append(list(map(int,input().split())))
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 row in A :
    for a in row :
        if a == -1 or a == 1 :
            continue
        else :
            ans += C[a][1]
print(ans)

Submission status: Runtime Error

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

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

print(ans)

Submission status: Runtime Error

Solution code:
h,w = map(int,raw_input().split())
d = [map(int,raw_input().split()) for i 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])
arr = [map(int,raw_input().split()) for i in range(h)]

print sum(sum(d[a][1] if a>=0 else 0 for a in aa) for aa in arr)

Submission status: Runtime Error

Solution code:
import math

#グラフの作成   
def make_list(V,E):
 
    edges = []
    path=[[0]*E for i in range(V) ]   #ルート作成に必要になる
    
    for i in range(V):
        a=[int(x) for x in str(input()).split()]
        for j in range(len(a)):
            #print("j",j)
            path[i][j]=i
            if j!= i and a[j]==0:
                a[j]=2000
                path[i][j]=-2000
	
        edges.append((a))    #  有効辺グラフ
	

   
     
    return edges ,path


def mainasu_sycle(dist):   #負のサイクルがあるか確認する    第一引数: 重みを含む配列  実装を確認していない
    
    for i in range (0,len(dist)):
       if dist[i][i] != 0:
        print ("Negative cycle at : ", i+1)




#最短経路をたどる
def ConstructPath(p, i, j):
    i,j = int(i), int(j)
    print("i,j:",i,j)
    if(i==j):
      print (i,)
    elif(p[i][j] == -30000):
      print (i,'-',j)
    else:
      ConstructPath(p, i, p[i][j]);
      print(j,)




#フロイド・ワーシャル
def warshall_floyd(glath,path):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
                                   path[i][j] = path[k][j]
				#glath[i][j]= min(int(glath[i][j]),int(glath[i][k])+int(glath[k][j]))
				
	return glath,path





H, W = [int(x) for x in str(input()).split()]  #グラフの大きさ 

cost_graph,graph=make_list(10,10)
wall ,wall_graph= make_list(H,W)
    #print(cost_graph)

un_label=[]
for i in wall:
   for j in i: 
            if j !=-1 and j!=1:
                 un_label.append(j)
cost=0
 
all_cost,all_graph=warshall_floyd(cost_graph,graph)
    
   

for i in un_label:
        cost+=all_cost[i][1]

print(cost)

Submission status: Runtime Error

Solution code:
import math

#グラフの作成   
def make_list(V,E):
 
    edges = []
    path=[[0]*E for i in range(V) ]   #ルート作成に必要になる
    
    for i in range(V):
        a=[int(x) for x in str(input()).split()]
        for j in range(len(a)):
            #print("j",j)
            path[i][j]=i
            if j!= i and a[j]==0:
                a[j]=30000
                path[i][j]=-3000
	
        edges.append((a))    #  有効辺グラフ
	

   
     
    return edges ,path


def mainasu_sycle(dist):   #負のサイクルがあるか確認する    第一引数: 重みを含む配列  実装を確認していない
    
    for i in range (0,len(dist)):
       if dist[i][i] != 0:
        print ("Negative cycle at : ", i+1)




#最短経路をたどる
def ConstructPath(p, i, j):
    i,j = int(i), int(j)
    print("i,j:",i,j)
    if(i==j):
      print (i,)
    elif(p[i][j] == -30000):
      print (i,'-',j)
    else:
      ConstructPath(p, i, p[i][j]);
      print(j,)




#フロイド・ワーシャル
def warshall_floyd(glath,path):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
                                   path[i][j] = path[k][j]
				#glath[i][j]= min(int(glath[i][j]),int(glath[i][k])+int(glath[k][j]))
				
	return glath,path






if __name__ == "__main__":
    H, W = [int(x) for x in str(input()).split()]  #グラフの大きさ 

    cost_graph,graph=make_list(10,10)
    wall ,wall_graph= make_list(H,W)
    #print(cost_graph)

    un_label=[]
    for i in wall:
       for j in i: 
            if j !=-1 and j!=1:
                 un_label.append(j)
    cost=0
 
    all_cost,all_graph=warshall_floyd(cost_graph,graph)
    
   

    for i in un_label:
        cost+=all_cost[i][1]

    print(cost)

Submission status: Runtime Error

Solution code:
import math

#グラフの作成   
def make_list(V,E):
 
    edges = []
    path=[[0]*E for i in range(V) ]   #ルート作成に必要になる
    
    for i in range(V):
        a = list(map(int, input().split()))
        for j in range(len(a)):
            #print("j",j)
            path[i][j]=i
            if j!= i and a[j]==0:
                a[j]=30000
                path[i][j]=-3000
	
        edges.append((a))    #  有効辺グラフ
	

   
     
    return edges ,path


def mainasu_sycle(dist):   #負のサイクルがあるか確認する    第一引数: 重みを含む配列  実装を確認していない
    
    for i in range (0,len(dist)):
       if dist[i][i] != 0:
        print ("Negative cycle at : ", i+1)




#最短経路をたどる
def ConstructPath(p, i, j):
    i,j = int(i), int(j)
    print("i,j:",i,j)
    if(i==j):
      print (i,)
    elif(p[i][j] == -30000):
      print (i,'-',j)
    else:
      ConstructPath(p, i, p[i][j]);
      print(j,)




#フロイド・ワーシャル
def warshall_floyd(glath,path):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
                                   path[i][j] = path[k][j]
				#glath[i][j]= min(int(glath[i][j]),int(glath[i][k])+int(glath[k][j]))
				
	return glath,path






if __name__ == "__main__":
    H, W = map(int, input().split())  #グラフの大きさ 

    cost_graph,graph=make_list(10,10)
    wall ,wall_graph= make_list(H,W)
   

    un_label=[]
    for i in wall:
       for j in i: 
            if j !=-1 and j!=1:
                 un_label.append(j)
    cost=0
 
    all_cost,all_graph=warshall_floyd(cost_graph,graph)
    
   

    for i in un_label:
        cost+=all_cost[i][1]

    print(cost)

Submission status: Runtime Error

Solution code:
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())))
# WF
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):
    cst[i]=djcstra(i,1,C)
print(sum(sum(C[i][1] for i in AA if i >= 0) for AA in A))

Submission status: Runtime Error

Solution code:
import networkx as nx

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

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

graph = nx.DiGraph()
# ノードを追加する
for i in range(10):
    graph.add_node(i)

# ノード間をエッジでつなぐ
for i in range(10):
    for j in range(10):
        if i==j:
            continue
        else:
            graph.add_edge(i, j, weight=clist[i][j])

# ダイクストラ法で最短経路を探す
power = 0
for h in range(H):
    for w in range(W):
        A = Alist[h][w]
        if A in [-1,1]:
            continue
        else:
            power += nx.dijkstra_path_length(graph, A, 1)
print(power)

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
c=[map(int,input().split()) for i in range(10)]
A=[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][j]<c[i][k]+c[k][j]:
        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: Runtime Error

Solution code:
import numpy as np
H,W = map(int,input().split())
H += -1
W += -1
import sys
ma = [[c for c in l.strip()] for l in sys.stdin]
ya = []
for s in ma:
  ya.extend(s)
count = ya.count(".")
ma = np.array(ma,"U10")
ma[0][0] = 1
que = []
que.append([0,0])
while len(que) > 0:
  y,x = que.pop(0)
  if y == H and x == W:
    break
  score = ma[y][x]
  try:
    if y != 0:
      y1 = ma[y-1][x] 
  except:
    pass
  try:
    y2 = ma[y+1][x]
  except:
    pass
  try:
    if x != 0:
      x1 = ma[y][x-1]
  except:
    pass
  try:
    x2 = ma[y][x+1] 
  except:
    pass
  try:
    if y1 == ".":
      ma[y-1][x] = str(int(score) + 1)
      que.append([y-1, x])
  except:
    pass
  try:
    if y2 == ".":
      ma[y+1][x] = str(int(score) + 1)
      que.append([y+1, x])
  except:
    pass
  try:
    if x1 == ".":
      ma[y][x-1] = str(int(score) + 1)
      que.append([y, x-1])
  except:
    pass
  try:
    if x2 == ".":
      ma[y][x+1] = str(int(score) + 1)
      que.append([y, x+1])
  except:
    pass
if ma[H][W] == ".":
  print(-1)
else:
  ten = int(ma[H][W])
  print(count - ten)