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:
H, W = map(int, input().split())
c = []
w = []
for i in range(10):
    c.append(list(map(int, input().split())))
for i in range(H):
    w.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])
p = 0
for r in w:
    for n in r:
        if n == -1:
            pass
        else:
            p += c[n][1]
print(p)

Submission status: Accepted

Solution code:
import heapq

H, W = map(int, input().split())
cs = [list(map(int, input().split())) for i in range(10)]
As = [list(map(int, input().split())) for i in range(H)]

N = 10
adj = [[] for i in range(N)]
for i in range(N):
    for j in range(N):
        adj[j].append((i, cs[i][j]))


cost = [float('inf') for i in range(N)]
cost[1] = 0

pq = []
heapq.heappush(pq, (0, 1))

while pq:
    c, vNow = heapq.heappop(pq)
    if c > cost[vNow]: continue

    for v2, w in adj[vNow]:
        if cost[vNow] + w < cost[v2]:
            cost[v2] = cost[vNow] + w
            heapq.heappush(pq, (cost[v2], v2))


ans = 0
for i in range(H):
    for j in range(W):
        if As[i][j] == -1:
            continue
        ans += cost[As[i][j]]

print(ans)

Submission status: Accepted

Solution code:
import heapq

def dijkstra(N,start, goal, E):
    """最短距離,経路を返すプログラム"""
    dist = [float('inf')] * N          #dist[i]:始点からの距離
    path = [tuple() for n in range(N)] #path[i]:(start,...,i)までの経路をカンマで区切ったもの
    dist[start] = 0
    path[start] = (start, )            
    pq = [(0, path[start])]

    while pq:
        di, pathi = heapq.heappop(pq)
        v = pathi[-1]

        if v == goal:
            return di

        #辺を全部見る
        for vertex, weight in E[v].items():
            new_di = di + weight
            if (new_di < dist[vertex]) or (new_di == dist[vertex] and pathi + (vertex, ) < path[vertex]):
                dist[vertex] = new_di
                path[vertex] = pathi + (vertex, )
                heapq.heappush(pq, (new_di, path[vertex]))



N = 10
H,W = map(int, input().split())
E = [dict() for i in range(10)]
ans = 0

tank = [0] * 10
for i in range(10):
    tmp = list(map(int,input().split(" ")))
    for j in range(10):
        E[i][j] = tmp[j]

for i in range(H):
    A = list(map(int,input().split(" ")))
    for j in range(W):
        if abs(A[j]) != 1:
            if tank[A[j]] == 0: 
                tank[A[j]] = dijkstra(N,A[j],1,E)

            ans += tank[A[j]]

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-        
import numpy as np
from collections import Counter

h, w = list(map(int,input().split()))
graph = np.zeros((10,10)).astype('int32')
a = np.zeros((h,w)).astype('int32')
for i in range(10):
    graph[i] = list(map(int,input().split()))
for i in range(h):
    a[i] = list(map(int,input().split()))

e, v = 90, 10
path = np.zeros((v,v)).astype('uint32')

for i in range(v):
    for j in range(v):
            path[i][j] = j
            
for k in range(v):
    for i in range(v):
        for j in range(v):
            if(graph[i][k]+graph[k][j]<graph[i][j]):
                graph[i][j] = graph[i][k]+graph[k][j]
                path[i][j] = path[i][k]
                
            
apy = a.ravel().tolist()
cnt = Counter(apy)
ans = 0
for i in range(10):
    ans += cnt[i]*graph[i][1]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict
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)]


cost = dict()

#d= defaultdict(int)
d = Counter()

for a in A:
    for i in a:
        if i==-1 or i==1:
            continue
        else:
            d[i]+=1




def search(glaph, start, goal):
    def get_path(start, goal, prev):
        path = []
        now = goal
        path.append(now)
        while True:
            path.append(prev[now])
            if prev[now] == start: break
            now = prev[now]
        path.reverse()
        return path

    MAX_VAL = 0x10000000
    g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    return [get_path(start, goal, prev), cost[goal]]
ans = 0
for key in d:
    ans += d[key]*search(C,key,1)[1]
print(ans)

Submission status: Accepted

Solution code:
# python3
# utf-8

import itertools

rows_nr, cols_nr = (int(x) for x in input().split())
d1___d2___cost = []
for i in range(10):
    d1___d2___cost_i___j = [int(x) for x in input().split()]
    d1___d2___cost.append(d1___d2___cost_i___j)
r_c___value = []
for row in range(rows_nr):
    c___value = [int(x) for x in input().split()]
    r_c___value.append(c___value)

f = d1___d2___cost
for i, v, u in itertools.product(range(10), repeat=3):
    f[u][v] = min(f[u][v], f[u][i] + f[i][v])
ans = 0
for row in r_c___value:
    for value in row:
        if value == -1:
            continue
        ans += f[value][1]
print(ans)

Submission status: Accepted

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

o = [c[n][1] for n in range(10)]

for _ in range(10):
    for i in range(10):
        for t in range(10):
            o[i] = min(o[i], c[i][t] + o[t])

print(sum([o[a] for a in A if a >= 0]))

Submission status: Accepted

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

ans = 0
for i in range(h):
    v = map(int, input().split())
    for x in v :
        if x >= 0 : ans += d[x][1]

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict
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)]


cost = dict()

#d= defaultdict(int)
d = Counter()

for a in A:
    for i in a:
        if i==-1 or i==1:
            continue
        else:
            d[i]+=1

def get_path(start, goal, prev):
    path = []
    now = goal
    path.append(now)
    while True:
        path.append(prev[now])
        if prev[now] == start: break
        now = prev[now]
    path.reverse()
    return path

def search(glaph, start, goal):
    MAX_VAL = 0x10000000
    g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    return [get_path(start, goal, prev), cost[goal]]
ans = 0
for key in d:
    ans += d[key]*search(C,key,1)[1]
print(ans)

Submission status: Accepted

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

import itertools

NUM_TYPES = 10
INVALID = -1


def in_place_min_costs(min_dist, num_vs=NUM_TYPES):
    for k, i, j in itertools.product(range(num_vs), repeat=3):
        min_dist[i][j] = min(min_dist[i][j], min_dist[i][k] + min_dist[k][j])


def solve(h, w, cs, board):
    in_place_min_costs(cs)
    res = 0
    for i, j in itertools.product(range(h), range(w)):
        b = board[i][j]
        if b != INVALID:
            res += cs[b][1]
    return res


def main():
    h, w = (int(x) for x in input().split())
    cs = [[int(x) for x in input().split()] for _ in range(NUM_TYPES)]
    board = [[int(x) for x in input().split()] for _ in range(h)]
    res = solve(h, w, cs, board)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

count_ = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for _ in range(H):
    for w in map(int, input().split()):
        if w >= 0:
            count_[w] += 1

# minimum cost
DP = [1000]*10
DP[1] = 0

end = 0
while end == 0:
    end = 1
    for i in range(10):
        a = min([C[i][j] + DP[j] for j in range(10)])
        if a < DP[i]:
            end = 0
            DP[i] = a
            
print(sum([DP[j]*count_[j] for j in range(10)]))

Submission status: Accepted

Solution code:
h,w = map(int,raw_input().split())
c = []
dist = []
for i in xrange(10):
    c.append(map(int,raw_input().split()))
    dist.append([100000000]*10)
a = []
for i in xrange(h):
    a.append(map(int,raw_input().split()))

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

cost = 0
for i in xrange(h):
    for j in xrange(w):
        if a[i][j] != -1:
            cost += dist[a[i][j]][1]
print cost

Submission status: Accepted

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

for _ in range(100):
    for u in range(10):
        for v in range(10):
            for w in range(10):
                c[u][w] = min(c[u][w], c[u][v] + c[v][w])

ans = 0
for ai in a:
    for aij in ai:
        if abs(aij) != 1:
            ans += c[aij][1]
print(ans)

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H,W = map(int, raw_input().split())
c = [map(int, raw_input().split()) for _ in range(10)]
A = [map(int, raw_input().split()) for _ 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])
print sum(sum(c[a][1] if a>=0 else 0 for a in aa) for aa in A)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())

a = []
for i in range(10):
	a.append(map(int, raw_input().split()))

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

s = 0
for i in range(n):
	for x in map(int, raw_input().split()):
		if x != -1:
			s += a[x][1]
print s

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

h, w = na()
g = []
for i in range(10):
    g.append(na())

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

ret = 0
for i in range(h):
    row = na()
    for v in row:
       if v >= 0:
           ret += g[v][1]
print(ret)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(10)]
A = [list(map(int, input().split())) for _ in range(H)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            C[i][j] = min(C[i][j], C[i][k] + C[k][j])
print(sum([sum(map(lambda a: 0 if a == -1 else C[a][1], row)) for row in A]))

Submission status: Accepted

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

Submission status: Runtime Error

Solution code:
from networkx import *
h,w=map(int,input().split());r=range(10);G=DiGraph();G.add_nodes_from(r);C=[[*map(int,input().split())]for _ in "_"*10];G.add_weighted_edges_from([(i,j,C[i][j])for i in r for j in r]);S=[single_source_dijkstra_path_length(G,i)[1]for i in r];A=[[*map(int,input().split())]for _ in r];print(sum(S[abs(x)] for a in A for x in a))

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

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):
        uf A[h][w] != -1:
        ans += c[A[h][w]][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)] 

# 0,(1),2,3,...,9に対して1にするための最小コストを求める
INF = 10 ** 4
d = c.copy()
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])


res = 0
for arr in A:
    for a in arr:
        if a == 1 or a == -1:
            continue
        else:
            res += d[a][1]

print(res)

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

    counter = Counter(A)

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np

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

# ワーシャルフロイド法で更新がなくなるまで更新
while True:
    prev = copy.deepcopy(dp)
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if i == j:
                    continue
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    if prev != dp:
        break
    prev = dp

arr = arr.flatten()

print(sum([dp[x][1] for x in arr if x != -1 or x != 1]))

Submission status: Runtime Error

Solution code:
H, W= map(int, input().split())
minpath = [[float("inf")]*10 for _ in range(10)]
path = [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):
            minpath[j][k] = min(minpath[j][k], path[j][i]+path[i][k])
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 += minpath[j][1]
print(ans)

Submission status: Runtime Error

Solution code:
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

Submission status: Runtime Error

Solution code:
#! env/bin/local python3
# -*- coding: utf-8 -*-

import numpy as np

inputs: list = []

while True:
    try:
        inputs.append([int(i) for i in input().split()])
    except EOFError:
        break

h, w = inputs[0]
c = inputs[1: 11]
a = inputs[11:]

number_of_edge = 10
number_of_node = 10

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

target = []
for ca in a:
    target += ca
# delete -1
target = [ta for ta in target if np.abs(ta) != 1]
results = 0
for t in target:
    results += c[t][1]

print(results)

Submission status: Runtime Error

Solution code:
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor, gcd
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10

    H,W = LMIIS()
    C = []
    for i in range(10):
        C.append(LMIIS())
    A = []
    for i in range(H):
        A.append(LMIIS())
    
    from copy import deepcopy
    minC = deepcopy(C)
    for i in range(10):
        for j in range(10):
            for k in range(10):
                if minC[i][j] + minC[j][k] < minC[i][k]:
                    minC[i][k] = minC[i][j] + minC[j][k]
    
    ans = 0
    for line in A:
        for a in line:
            if a != -1 and a!= 1:
                ans += minC[a][1]
    print(ans)


    
main()

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
import collections
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

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

array = np.array(c)

count = []

for i in range(H):
    for j in range(W):
        count.append(A[i][j])

counter = collections.Counter(count)
cost = [0]*10

for i in counter.keys():
    if i == -1:
        continue
    cost[i] = shortest_path(array, indices=i)[1]

ans = 0
for k, v in counter.items():
    if k == -1:
        continue
    ans += (cost[k]*v)

print(int(ans))

Submission status: Runtime Error

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

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

d = dict()
nums = [i for i in range(10) if i != 1]

q = [[[1], 0]]

while q:
    tmp = q.pop()
    num, cost = tmp[0], tmp[1]
    key = str(num[-1]) + "_1"
    if d.get(key):
        d[key] = min(d[key], cost)
    else:
        d[key] = cost
    if len(num) < 10:
        for n in nums:
            num_tmp = num.copy()
            if n not in set(num_tmp):
                num_tmp.append(n)
                q.append([num_tmp, cost + c[num_tmp[-1]][num_tmp[-2]]])

ans = 0
for i in range(H):
    for j in range(W):
        tmp = grid[i - 1][j - 1] 
        if tmp >= 0:
            ans += d[str(tmp) + "_1"]
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, deque

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

d = defaultdict(lambda: float("inf"))
d["1_1"] = 0
nums = [i for i in range(10) if i != 1]

q = deque([[[1], 0]])

while q:
    tmp = q.pop()
    num, cost = tmp[0], tmp[1]
    if len(num) > 1:
        key = str(num[-1]) + "_1"
        d[key] = min(d[key], cost)
    if len(num) < 10:
        for n in nums:
            num_tmp = num.copy()
            if n not in set(num_tmp):
                num_tmp.append(n)
                q.append([num_tmp, cost + c[n][num_tmp[-2]]])

ans = 0
for i in range(H):
    for j in range(W):
        tmp = grid[i - 1][j - 1] 
        if tmp >= 0:
            ans += d[str(tmp) + "_1"]
print(ans)

Submission status: Runtime Error

Solution code:
def abc079_d():
    inp = iter(map(int, read().split()))
    H, W = next(inp), next(inp)
    adj_mtx = [[next(inp) for _ in range(10)] for _ in range(10)]
    grid = [[next(inp) for _ in range(W)] for _ in range(H)]

    def floyd_warshall(W):
        ''' ワーシャルフロイド法、全頂点間の最短距離 '''
        n = len(W)  # 頂点の数
        # DPで全頂点間の最短距離を求める
        for k in range(n):
            for u in range(n):
                for v in range(n):
                    W[u][v] = min(W[u][v], W[u][k] + W[k][v])
        return W

    min_dist = floyd_warshall(adj_mtx)

    # グリッドの数字が-1と1以外はコスト発生するため足していく
    ans = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == -1 or grid[i][j] == 1:
                continue
            ans += min_dist[grid[i][j]][1]
    print(ans)

abc079_d()

Submission status: Runtime Error

Solution code:
def abc079_d():
    inp = iter(map(int, read().split()))
    H, W = next(inp), next(inp)
    adj_mtx = [[next(inp) for _ in range(10)] for _ in range(10)]
    grid = [[next(inp) for _ in range(W)] for _ in range(H)]

    import heapq
    def dijkstra(start, W):
        ''' スタート地点から到達可能なすべての頂点への最短距離を返す
            Pythonで学ぶアルゴリズムとデータ構造 P.111 一部変更
        '''
        # 仮の最短距離をinfに設定
        inf = 10**9
        distance_list = [inf] * len(W)
        # スタートの頂点だけ距離を0にする
        distance_list[start] = 0
        # 最短距離が確定した点
        done_list = []
        # 次に処理する頂点を決めるためのヒープ
        wait_heap = []
        for i, d in enumerate(distance_list):
            # (スタートからの距離, 頂点) のタプル
            heapq.heappush(wait_heap, (d, i))
        # ヒープが空になるまで処理を続ける
        while wait_heap:
            p = heapq.heappop(wait_heap)
            i = p[1]
            if i in done_list:
                continue
            # この時点でスタートからiへの距離が確定する
            done_list.append(i)
            # iに隣接するすべての頂点に対する処理
            for j, x in enumerate(W[i]):
                if x > -1 and j not in done_list:
                    # 緩和
                    d = min(distance_list[j], distance_list[i] + x)
                    distance_list[j] = d
                    # jへの仮の最短距離をdとしてヒープに追加
                    heapq.heappush(wait_heap, (d, j))
        return distance_list

    # 各点から1への距離(コスト)
    dist_to_1 = [None] * 10
    for i in range(10):
        dist_to_1[i] = dijkstra(i, adj_mtx)[1]

    # グリッドの数字が-1と1以外はコスト発生するため足していく
    ans = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == -1 or grid[i][j] == 1:
                continue
            ans += dist_to_1[grid[i][j]]
    print(ans)

abc079_d()

Submission status: Runtime Error

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

d, p = floyd_warshall(csgraph=graph, directed=True, return_predecessors=True)
#print(d)
dic={-1:0}
for i in range(10):
    dic[i]=d[i][1]
ans=0
for i in range(h):
    for j in map(int,input().split()):
        ans+=dic[j]
print(int(ans))

Submission status: Runtime Error

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

'''重み0の辺は自動で消されてしまうので注意'''
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
inf = 10 ** 10
G = csgraph_from_dense(c, null_value = 0)
d = floyd_warshall(G)
cost = 0

for i in range(h):
    for j in range(w):
        temp = a[i][j]
        if temp == -1:continue
        cost += d[temp][1]
print(int(cost))

Submission status: Runtime Error

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

'''重み0の辺は自動で消されてしまうので注意'''
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
inf = 10 ** 10
G = csgraph_from_dense(c, null_value = 10 ** 10)
d = floyd_warshall(G)
cost = 0

for i in range(h):
    for j in range(w):
        temp = a[i][j]
        if temp == -1:continue
        cost += d[temp][1]
print(int(cost))

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

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

import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


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

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

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

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

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


resolve()

Submission status: Runtime Error

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

import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


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

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

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

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

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

Submission status: Runtime Error

Solution code:
# import bisect
# from collections import Counter, deque # https://note.nkmk.me/python-scipy-connected-components/
# from copy import copy, deepcopy
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


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

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

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

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

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