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())
N=10
c=[[int(i) for i in input().split()] for i in range(N)]
A=[[int(i) for i in input().split()] for i in range(H)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            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: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
H, W = map(int, input().split())
c = [None] * 10
for i in range(10):
    c[i] = [int(cij) for cij in input().split()]
D = floyd_warshall(c)
cost = 0
for i in range(H):
    for Aij in input().split():
        Aij = int(Aij)
        if Aij == -1:
            continue
        cost += D[Aij][1]
print(int(cost))

Submission status: Accepted

Solution code:
from itertools import product

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

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

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

Submission status: Accepted

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

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

v=[[l[j][1] if j>=0 else 0 for j in i] for i in o]
print(sum(map(sum,v)))

Submission status: Accepted

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

Submission status: Accepted

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: Accepted

Solution code:
def d_wall(H, W, C, A):
    import scipy.sparse
    # cost[i][j]:数字iからjに移行するための最小コスト(float64で格納される)
    cost = scipy.sparse.csgraph.floyd_warshall(C)

    # 壁の各数字ごとにコストの値を参照、和を取る
    ans = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] != -1:
                ans += cost[A[h][w]][1]  # 壁の数字から1へ変えるための最小コスト
    return int(ans)

H,W = [int(i) for i in input().split()]
C = [[int(i) for i in input().split()] for j in range(10)]
A = [[int(i) for i in input().split()] for j in range(H)]
print(d_wall(H, W, C, A))

Submission status: Accepted

Solution code:
# http://dai1741.github.io/maximum-algo-2012/docs/shortest-path/
H, W = map(int, input().split())

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

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

# Distance with init
#D = [[1e9] * 10 for i in range(10)]
#for i in range(10):
#  D[i][i] = 0

# warshal-floyd
# i:middle, j:from, k:to
for i in range(10): 
  for j in range(10): 
    for k in range(10):
      if C[j][k] > C[j][i] + C[i][k]:
        C[j][k] = C[j][i] + C[i][k]

ans = 0
for i in range(H):
  for j in range(W):
    if A[i][j] >= 0:
      ans += C[A[i][j]][1]

print(ans)

Submission status: Accepted

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

def dijkstra(s):
    d = [float("inf") for _ in range(0,10)]
    d[s] = 0
    q = []
    q.append((s,g[s]))
    while len(q) > 0:
        start,edge = q.pop(0)
        for to,cost in edge:
            if d[to] > d[start] + cost:
                d[to] = d[start] + cost
                q.append((to,g[to]))
    return d[1]

d = []
for i in range(0,10):
    d.append(dijkstra(i))
ans = 0
for i in range(0,h):
    a = list(map(int,input().split()))
    for j in range(0,w):
        if a[j] != -1:
            ans += d[a[j]]
print(ans)

Submission status: Accepted

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: Accepted

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

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

H,W = inpl()

lines = defaultdict(set)

for i in range(10):
	li = inpl()
	for j,c in enumerate(li):
		lines[j].add((i,c))

def search (s,w_0): #s->t
	global weight
	global q
	for line in list(lines[s]):
		t = line[0]
		w = w_0 + line[1]
		if weight[t] > w:
			heapq.heappush(q, [w,t])
			weight[t] = w

s = 1
weight = [INF]*10
weight[s] = 0
q = [[0,s]]
heapq.heapify(q)
while q:
	w,n = heapq.heappop(q)
	search(n,w)

ans = 0
for i in range(H):
	li = inpl()
	for l in li:
		if l == -1:
			continue
		else:
			ans += weight[l]

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)]
ans = 0

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

for i in range(H):
    for j in range(W):
        if A[i][j] == -1 or A[i][j] == 1:
            continue
        else:
            ans += c[A[i][j]][1]
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

#1. 入力
H,W = map(int, input().split())

INF = float("inf")
graph1 = []

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

graph2 = [[] for _ in range(10)]
for i in range(10):
    for j in range(10):
        graph2[i].append((graph1[i][j], j))

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

#2. ダイクストラ
def dijkstra(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

dist_to1 = []
for i in range(10):
    dist = dijkstra(graph2, 10, i)
    dist_to1.append(dist[1])

ans = 0
for h in range(H):
    for w in range(W):
        if A[h][w] == -1:
            continue
        else:
            ans += dist_to1[A[h][w]]
    
print(ans)

Submission status: Accepted

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

import heapq
def dijkstra(adj, n, st=1):
    dj = [2**64] * (n + 1)
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        for tn, lc in adj[fn]:
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                heapq.heappush(q, (dj[tn], tn))
    return dj

adj = {}
for j in range(10):
    t = []
    for i in range(10):
        t.append([i, C[i][j]])
    adj[j] = t
costs = dijkstra(adj, 9, 1)

from itertools import chain
print(sum(costs[x] for x in chain(*A) if x != -1))

Submission status: Accepted

Solution code:
from collections import defaultdict
from scipy.sparse.csgraph import floyd_warshall
H, W = map(int, input().split())
C = []
for i in range(10):
    ci = [int(cij) for cij in input().split()]
    C.append(ci)

A = defaultdict(int)
for i in range(H):
    for Aij in input().split():
        A[int(Aij)] += 1
if -1 in A:
    del A[-1]

D = floyd_warshall(C)
cost = 0
for k, v in A.items():
    cost += D[k][1] * v
print(int(cost))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
C = [[int(x) for x in input().split()] for i in range(10)]
preC = [c[:] for c in C]
for l in range(10):
  postC = [c[:] for c in preC]
  for i in range(10):
    for j in range(10):
      for k in range(10):
        postC[i][j] = min(preC[i][k] + C[k][j], postC[i][j])
  preC = [c[:] for c in postC]
L = [postC[i][1] for i in range(10)]
A = [[int(x) for x in input().split()] for i in range(H)]
ans = 0
for Ai in A:
  for Aij in Ai:
    if Aij > -1:
      ans += L[Aij]
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def warshall_floyd(g):
    d = defaultdict(dict)
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v))
    V = set(V)
    for i in V:
        for j in V:
            if i in g and j in g[i]:
                d[i][j] = g[i][j]
            else:
                d[i][j] = sys.maxsize
    for k in g:
        for i in g:
            for j in g:
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

    return d


@mt
def slv(H, W, C, A):
    g = defaultdict(dict)
    for i in range(10):
        for j in range(10):
            g[i][j] = C[i][j]

    d = warshall_floyd(g)

    a = Counter()
    for r in A:
        for n in r:
            a[n] += 1

    ans = 0
    for k in a:
        if k != -1:
            ans += d[k][1] * a[k]
    return ans


def main():
    H, W = read_int_n()
    C = [read_int_n() for _ in range(10)]
    A = [read_int_n() for _ in range(H)]
    print(slv(H, W, C, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
INF = 10 ** 10
h, w = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(10)]

cost_to_one = []
for i in range(10):
  costs = [INF] * 10
  que = []
  heappush(que, (0, i))
  costs[i] = 0
  while que:
    dist, node = heappop(que)
    for to, v in enumerate(edges[node]):
      if costs[to] > dist + v:
        costs[to] = dist + v
        heappush(que, (dist + v, to))
  cost_to_one.append(costs[1])

cost_to_one.append(0)
ans = 0
for _ in range(h):
  lst = list(map(int, input().split()))
  for i in lst:
    ans += cost_to_one[i]

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 x in range(h)]

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:

h,w = list(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 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 a:
    for j in i:
        if j != -1:
            ans += c[j][1]
print(ans)

Submission status: Accepted

Solution code:
N, INF = 10, 1 << 40
M = [[INF for j in range(N)] for i in range(N)]
dist = [[INF for l in range(N)] for m in range(N)]


def dijkstra(s):
    check = [0 for i in range(N)]
    dist[s][s] = 0

    while True:
        min_cost, u = INF, -1
        for i in range(N):
            if check[i] != 2 and dist[s][i] < min_cost:
                min_cost = dist[s][i]
                u = i

        if min_cost == INF:
            break

        check[u] = 2

        for v in range(N):
            if check[v] != 2 and M[u][v] != INF:
                if dist[s][u] + M[u][v] < dist[s][v]:
                    dist[s][v] = dist[s][u] + M[u][v]
                    check[v] = 1


def main():
    h, w = map(int, input().split())
    for i in range(N):
        low = list(map(int, input().split()))
        for j in range(N):
            if low[j] != 0:
                M[i][j] = low[j]

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

    for i in range(N):
        dijkstra(i)

    cost = 0
    for i in range(h):
        for j in range(w):
            if grid[i][j] != -1:
                num = grid[i][j]
                cost += dist[num][1]

    print(cost)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
b=input().split(" ")
a0=input().split(" ")
a1=input().split(" ")
a2=input().split(" ")
a3=input().split(" ")
a4=input().split(" ")
a5=input().split(" ")
a6=input().split(" ")
a7=input().split(" ")
a8=input().split(" ")
a9=input().split(" ")
array=[a0,a1,a2,a3,a4,a5,a6,a7,a8,a9]
cost=0
for k in range(10):
	for i in range(10):
		for j in range(10):
			array[i][j]=min(int(array[i][j]),int(array[i][k])+int(array[k][j]))
for i in range(int(b[0])):
	lines=input().split()
	for j in range(int(b[1])):
		if int(lines[j])!=-1:
			cost+=int(array[int(lines[j])][1])
print(cost)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product

H, W = map(int, input().split())
c = [[int(x) for x in input().split()] for _ in range(10)]
A = defaultdict(int)
for _ in range(H):
    for x in input().split():
        x = int(x)
        if x != -1 and x != 1:
            A[x] += 1

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

ans = 0
for k, v in A.items():
    ans += c[k][1] * v
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product

H, W = map(int, input().split())
c = [[int(x) for x in input().split()] for _ in range(10)]
A = defaultdict(int)
for _ in range(H):
    for x in input().split():
        x = int(x)
        if x != -1 and x != 1:
            A[x] += 1

for _, i, j, k in product(range(10), range(10), range(10), range(10)):
    if i == 1 or k == 1:
        continue
    c[i][j] = min(c[i][j], c[i][k] + c[k][j])

ans = 0
for k, v in A.items():
    ans += c[k][1] * v
print(ans)

Submission status: Accepted

Solution code:
import math

#グラフの作成   
def make_list(V,E):
 
    edges = []
    path=[[float("inf")]*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 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: Accepted

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 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: Accepted

Solution code:
d=input().split(" ")
a0=input().split(" ")
a1=input().split(" ")
a2=input().split(" ")
a3=input().split(" ")
a4=input().split(" ")
a5=input().split(" ")
a6=input().split(" ")
a7=input().split(" ")
a8=input().split(" ")
a9=input().split(" ")
AA=[a0,a1,a2,a3,a4,a5,a6,a7,a8,a9]
stop=0
for k in range(10):
    for i in range(10):
        for j in range(10):
            AA[i][j]=min(int(AA[i][j]),int(AA[i][k])+int(AA[k][j]))
for i in range(int(d[0])):
    gear=input().split()
    for j in range(int(d[1])):
        if int(gear[j])!=-1:
            stop+=int(AA[int(gear[j])][1])
print(stop)

Submission status: Accepted

Solution code:
#Floyd-Warshall Algo


H,W=[int(x) for x in str(input()).split()]
c=[]
for i in range(0,10):
  c.append([int(x) for x in str(input()).split()])

A=[]
A.append([0 for i in range(0,W+1)])
for i in range(1,H+1):
  A.append([0]+[int(x) for x in str(input()).split()])

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


abc=[]
for i in range(0,10):
  abc.append(c[i][1])

count=0

for i in range(1,H+1):
  for j in range(1,W+1):
    if A[i][j]!=-1:
      count+=abc[A[i][j]]
print(count)

Submission status: Accepted

Solution code:
x=input().split()
h=int(x[0])
w=int(x[1])
c=[[]*10 for i in range(10)]
for i in range(10):
    y=input().split()
    x=0
    while x<10:
        y[x]=int(y[x])
        x=x+1
    c[i].extend(y)
    
a=[[]*w for i in range(h)]

for i in range(h):
    y=input().split()
    x=0
    while x<w:
        y[x]=int(y[x])
        x=x+1
    a[i].extend(y)
    
for k in range (10):
    for i in range(10):
        for j in range(10):
            c[i][j]=min(c[i][j], c[i][k]+c[k][j])
cost=0
for i in range(h):
    for j in range(w):
        if a[i][j]!=-1:
            cost=cost+c[a[i][j]][1]
print(cost)

Submission status: Accepted

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[j][k]=min(C[j][k], C[j][i]+C[i][k])
print(sum(sum(C[i][1] for i in AA if i >= 0) for AA in A))

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

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split())
C = []
for i in range(10):
    C.append(list(map(int, input().split())))
CT = np.array(C).T
W = [0] * 10
for i in range(H):
    for j in map(int, input().split()):
        if j != -1:
            W[j] += 1

D = [0] * 10
Open = list(CT[1])
Open[1] = -1
for j in range(9):
    p = min([l for l in enumerate(Open) if l[1] != -1], key=lambda x: x[1])
    D[p[0]] = p[1]
    Open[p[0]] = -1
    for i in range(10):
        Open[i] = min(Open[i], CT[p[0]][i] + p[1])
ans = 0
for i in range(10):
    ans += D[i] * W[i]
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
H,W = map(int,input().split())
inf=10**10
#[k][j][i]
dp=[[[inf]*10 for i in range(10)]for i in range(11)]
for j in range(10):
    c=[int(k) for k in input().split()]
    for i in range(10):
        dp[0][i][j]=c[i]#jiへのコスト

A=[[int(i) for i in input().split()] for i in range(H)]
for k in range(1,11):
    for j in range(10):
        for i in range(10):
            dp[k][j][i]=min(dp[k-1][j][i],dp[k-1][j][k-1]+dp[k-1][k-1][i])
ans =0
for i in range(W):
    for j in range(H):
        if A[j][i]!=-1 and A[j][i]!=1:
            ans += dp[10][1][A[j][i]]
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
H,W = map(int,input().split())
table=[[] for i in range(10)]
for i in range(10):
    c=[int(k) for k in input().split()]
    for j in range(10):
        if i==j:
            continue
        table[j].append([i,c[j]])#jからiに行くコスト
A=[[int(i) for i in input().split()] for i in range(H)]

#ダイクストラ
kei=[]
val=[10**9]*(10)
val[1]=0
heappush(kei,(0,1))
while kei:
    d,i = heappop(kei)
    if d > val[i]:
        continue
    for x,q in table[i]:
        if val[x]>val[i]+q:
            val[x]=val[i]+q
            heappush(kei,(val[x],x))
ans =0
for i in range(W):
    for j in range(H):
        if A[j][i]!=-1 and A[j][i]!=1:
            ans += val[A[j][i]]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, deque
import heapq


def Dijkstra(C, s):
    q = []
    inf = float("inf")
    f = [inf] * 11
    f[-1] = 0
    f[s] = 0
    heapq.heappush(q, (0, s))
    while len(q) != 0:
        # print(q)
        # print(f)
        cost, index = heapq.heappop(q)
        if index == 1:
            return f[index]
        if f[index] < cost:
            continue
        for i in range(10):
            if cost + C[index][i] < f[i]:
                f[i] = cost + C[index][i]
                heapq.heappush(q, (f[i], i))
    return "hoge"


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

c = Counter()
for i in range(H):
    for j in range(W):
        c[A[i][j]] += 1
D = []
for i in range(10):
    D.append(Dijkstra(C, i))
D.append(0)
s = 0
for i, j in c.items():
    s += D[i] * j

print(s)

Submission status: Accepted

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

c=[None]*10

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

A=[]

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

minc=[None]*10

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

#mincを求める.

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



NUM=[0]*10

for i in range(H*W):
    if A[i]!=-1:
        NUM[A[i]]+=1

ANS=0
for i in range(10):
    ANS+=NUM[i]*minc[i][1]

print(ANS)

Submission status: Accepted

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

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

cmin += [[[0]*10 for j in range(10)] for i in range(4)]

for i in range(4):
    for j in range(10):
        for k in range(10):
            cmin[i+1][j][k] = min([cmin[i][j][l] + cmin[i][l][k] for l in range(10)])

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

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
costs = [list(map(int, input().split())) for _ in range(10)]
wall = [list(map(int, input().split())) for _ in range(H)]
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])

d = {-1: 0, 0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
for i in wall:
    for n in range(-1, 10):
        d[n] += i.count(n)
min_cost = 0
for i in range(-1, 10):
    if i == 1:
        continue
    if i == -1:
        min_cost += d[i] * costs[1][1]
    else:
        min_cost += d[i] * costs[i][1]
print(min_cost)

Submission status: Accepted

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

c = []
for _ 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][k] + c[k][j], c[i][j])

A = []

for _ in range(0, H):
    A.append(list(map(int, input().split())))

ans = 0

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

print(ans)

Submission status: Accepted

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

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 rA in A:
    for n in rA:
        if n >= 0:
            ans += c[n][1]

print(ans)

Submission status: Accepted

Solution code:
H,W = list(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())))

def Warshall_Floyd():
    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])

Warshall_Floyd()

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)