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:
class WarshallFloyd:
    def __init__(self,n):
        self.n = n
        self.inf = float('inf')
        self.d = [[self.inf for _ in range(n)] for _ in range(n)]
        for i in range(self.n):
            self.d[i][i] = 0
    def register(self,v1,v2,l,multiple=True):
        self.d[v1][v2] = l
        if multiple:
            self.d[v2][v1] = l
    def solve(self):
        for i in range(self.n):
            for j in range(self.n):
                for k in range(self.n):
                    self.d[j][k] = min(self.d[j][k],self.d[j][i]+self.d[i][k])
        return self.d
H,W = map(int,input().split())
C = []
A = []
WF = WarshallFloyd(10)
for i in range(10):
    C.append(list(map(int,input().split())))
for i in range(10):
    for j in range(10):
        WF.register(i,j,C[i][j],multiple=False)
C = WF.solve()
for i in range(H):
    A.append(list(map(int,input().split())))
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)

Submission status: Accepted

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

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

numbers=[0 for i in range(0,10)]
for i in range(0,H):
    for j in range(0,W):
        if A[i][j]!=-1:
            numbers[A[i][j]]+=1

print(sum(numbers[i]*C[i][1] for i in range(0,10)))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

######################################################

INF = 1e10
H, W = list(map(int, input().split()))

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

for i in range(10):
    for j, v in enumerate([int(_) for _ in input().split()]):
        dp[i][j] = v

for k in range(10):
    for i in range(10):
        for j in range(10):
            # k経由でiからjへ
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
ans = 0
for h in range(H):
    for w in [int(_) for _ in input().split()]:
        if w == -1: continue
        ans += dp[w][1]
print(ans)

Submission status: Accepted

Solution code:

def search(start: int, visited: list, power: list, min_power: int, min_powers: int) -> int:
    minimum = 10**4
    if min_powers[start] != -1:
        return min_powers[start] + min_power
    if visited[1] == True:
        #print(f'{min_power=}')
        return min_power
    for i, v in enumerate(visited):
        if not v:
            visited[i] = True
            min_power += power[start][i]

            #min_powers[i] = search(i,visited,power,min_power,min_powers)
            minimum = min(minimum, search(i,visited,power,min_power,min_powers))

            visited[i] = False
            min_power -= power[start][i]
            #print(f'{minimum=}')
    return minimum


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

power = [[] for _ in range(10)]

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

world = [[] for _ in range(H)]

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

min_powers = [-1] * 10
visited = [False] * 10

#print(f'{power[8][4]=}')
for i in range(10):
    min_power = 0
    visited[i] = True
    min_powers[i] = search(i,visited,power,min_power,min_powers)
    visited[i] = False
    #visited = [False] * 10
for i in range(10):
    pass
    #print(f'{i=}, {min_powers[i]=}')
ans = 0
for wor in world:
    for w in wor:
        if w != -1:
            ans += min_powers[w]

print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
c=[list(map(int,input().split())) for i in range(10)]
Gd=[]
for i in range(H):
  Gd=Gd+list(map(int,input().split()))
dp = [[[10000]*10 for i in range(10)] for t in range(10)]
dp[0] = c[:]
for t in range(1,10):
  for i in range(10):
    for j in range(10):
      for k in range(10):
        dp[t][i][j]=min(dp[t][i][j],dp[t-1][i][k]+c[k][j])
ret = 0
for i in Gd:
  if i>=0:
    ret+=dp[-1][i][1]
print(ret)

Submission status: Accepted

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


def dfs(now, mp, rest):
    if now == 1:
        return mp
    ret = [
        dfs(p, mp + cost[now][p], rest[:i] + rest[i+1:]) for i, p in enumerate(rest)
    ]
    return min(ret)


r = list(range(10))
magic = [dfs(i, 0, r[:i] + r[i+1:]) for i in range(10)]

ans = 0
for _ in range(h):
    x = list(map(int, input().split()))
    for a_ij in x:
        if a_ij == -1:
            pass
        else:
            ans += magic[a_ij]
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
C = [[0 for _ in range(10)] for _ in range(10)]
for i in range(10):
    for j, c in enumerate(input().split()):
        C[i][j] = int(c)
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 A in input().split():
        A = int(A)
        if A >= 0:
            ans += C[A][1]
# print(C)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
CC = [list(map(int, input().split())) for _ in range(10)]
AA = [list(map(int, input().split())) for _ in range(h)]

total = 0
memo = [-1] * 10
for A in AA:
    for a in A:
        if a == -1:
            continue
        if memo[a] != -1:
            total += memo[a]
        else:
            best = CC[a][1]
            q = deque()
            q.append((a, 0))
            used = {a}
            while q:
                node, cost = q.popleft()
                for to in range(10):
                    new_cost = cost + CC[node][to]
                    if to == node or new_cost >= best:
                        continue
                    if to == 1:
                        if new_cost < best:
                            best = new_cost
                    else:
                        q.append((to, new_cost))
                        used.add(to)
            memo[a] = best
            total += memo[a]
print(total)

Submission status: Accepted

Solution code:
import heapq as hq
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)]

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

dis = [10**10] * 10
dis[1] = 0
q = []
hq.heappush(q, (0,1))

while q:
    dis1,p = hq.heappop(q)
    for dis2,p2 in edges[p]:
        if dis[p2] > dis[p] + dis2:
            dis[p2] = dis[p] + dis2
            hq.heappush(q, (dis[p2], p2))

ans = 0

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

print(ans)

Submission status: Accepted

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

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

answer = 0
for a in A:
    for aa in a:
        if aa != -1:
            answer += C[aa][1]

print(answer)

Submission status: Accepted

Solution code:
def warshall_floyd(d):
    n = len(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


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

d = warshall_floyd(c)
ans = 0
for _ in range(H):
    line = map(int, input().split())
    for v in line:
        if v != -1:
            ans += d[v][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 = [list(map(int,input().split())) for _ in range(H)]

N  = 10
d = c
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])

ans = 0
for aa in A:
    for a in aa:
        if a!=-1:
           ans += d[a][1]
           
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    # sys.stdin = open("Sample.txt")
    H, W = Scanner.map_int()
    C = Scanner.int_list_list(10)
    A = Scanner.int_list_list(H)

    for k in range(10):
        for i in range(10):
            for j in range(10):
                C[i][j] = min(C[i][j], C[i][k] + C[k][j])
    ans = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == -1:
                continue
            ans += C[A[h][w]][1]
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for k in range(10):
  for i in range(10):
    for j in range(10):
      if grid[i][k]+grid[k][j]<grid[i][j]:
        grid[i][j]=grid[i][k]+grid[k][j]
        
ans=0
for i in range(H):
  A=list(map(int,input().split()))
  for a in A:
    if a==-1:
      continue
    ans+=grid[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):
            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())

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

from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

G = csgraph_from_dense(c, null_value=0)

l = []
for i in range(10):
    d = dijkstra(G, indices=i)
    l.append(d[1])
ans = 0
for _ in range(H):
    A = list(map(int, input().split()))
    for a in A:
        if a != -1 and a != 1:
            ans += l[a]

print(int(ans))

Submission status: Accepted

Solution code:
import heapq

INF = 10**9

def solve():
  # n から 1への最短距離をもとめる
  H,W = map(int, input().split())
  graph = [list(map(int, input().split())) for _ in range(10)]
  search_table = [[i != 1 and i != j for i in range(10)] for j in range(10)]
  min_distance_n_to_1 = [INF]*10
  min_distance_n_to_1[1] = 0
  
  # 1から逆にたどっていく
  queue = [(min_distance_n_to_1[v], v) for v in range(10)]
  heapq.heapify(queue)

  while queue:
    _, dom = heapq.heappop(queue)
    # print(dom, min_distance_n_to_1)
    for i in range(10):
      # if not search_table[dom][i]: continue
      # search_table[dom][i] = False
      
      if min_distance_n_to_1[i] > min_distance_n_to_1[dom] + graph[i][dom]:
        min_distance_n_to_1[i] = min_distance_n_to_1[dom] + graph[i][dom]
        heapq.heappush(queue, (min_distance_n_to_1[i], i))

  # print(min_distance_n_to_1)
  ret = sum(sum(min_distance_n_to_1[int(Aij)] if int(Aij) != -1 else 0 for Aij in input().split()) for _ in range(H))
  print(ret)
  
solve()

Submission status: Accepted

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


H, W = map(int, input().split())
ls = [0]*10
cost = [[10**5]*10 for i in range(10)]
dist = [0]*10
for i in range(10):
  inf = [int(c) for c in input().split()]
  for j in range(10):
    cost[i][j] = inf[j]
dist = warshall_floyd(cost,10)
cnt = [0]*(12)
for i in range(H):
  inf = [int(c) for c in input().split()]
  for j in range(W):
    cnt[inf[j]] += 1
ans = 0
for i in range(10):
  ans += dist[i][1]*cnt[i]
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
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 = floyd_warshall(c)
ans = 0
for i in range(H):
    for j in range(W):
        if a[i][j] == -1 or a[i][j] == 1:
            continue
        else:
            ans += wf[a[i][j]][1]

print(int(ans))

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense

from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense
# [[10 ** 9, 1, 2],
#  [3, 10 ** 9, 2]
#  [10 ** 9, 4, 7]]


input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    edge = [[int(x) for x in input().split()] for _ in range(10)]
    A = [[int(x) for x in input().split()] for _ in range(H)]

    G = csgraph_from_dense(edge, null_value=0)
    d = floyd_warshall(G)

    ans = 0
    for a in A:
        for v in a:
            if v == -1:
                continue
            ans += d[v][1]

    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
h,w = map(int,readline().split())
lst1 = [list(map(int,readline().split())) for i in range(10)]

#まず、数字をiから１に変える時の最小コストを計算する。
from scipy.sparse.csgraph import shortest_path,floyd_warshall
from scipy.sparse import csr_matrix
lc = csr_matrix(lst1)
cost_lst = shortest_path(lc,method="FW")

#全探索でコストを求める。
ans = 0
for i in range(h):
    lst2 = list(map(int,readline().split()))
    for j in lst2:
        if j != -1:
            ans += cost_lst[j][1]

print(int(ans))

Submission status: Accepted

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

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

wall = []
for _ in range(h):
  wa = list(map(int, input().split()))
  wall.append(list(wa))
  
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])

total_cost = 0
for i in range(h):
  for j in range(w):
    num = wall[i][j]
    if num != -1:
      total_cost += c[num][1]
print(total_cost)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
cost=[list(map(int,input().split())) for i in range(10)]
wall=[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):
      cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])

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

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall

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

d=floyd_warshall(c)
ans=0
for i in range(h):
 for j in range(w):
  num=a[i][j]
  if num!=1 and num!=-1:
   ans+=d[num][1]
print(int(ans))

Submission status: Accepted

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

costs=[10**10]*10
costs[1]=0

used=[]
used.append(1)
now=1

while True:
    for i in range(0,10):
        if i in used:
            continue
        if costs[i] > c[i][now]+costs[now]:
            costs[i] = c[i][now]+costs[now]

    argmin=-1
    costmin=10**5
    for i in range(0,10):
        if i in used:
            continue
        if costs[i] < costmin:
            costmin=costs[i]
            argmin=i
    if argmin==-1:
        break
    now=argmin
    used.append(now)

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

Submission status: Accepted

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


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

ans=0
for i in wall:
    for j in i:
        if j!=-1 and j!=1:
            ans+=d[j][1]
print(ans)

Submission status: Accepted

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


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

ans=0
for i in wall:
    for j in i:
        if j!=-1 and j!=1:
            ans+=field[j][1]
print(ans)

Submission status: Accepted

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

# 各数字を1に書き換えるときの最小のコストを保持しておけば良い。
# どうやって最小のコストを保持する？→ダイクストラ的なdpを実装すれば良い
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix, lil_matrix
import numpy as np
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


H, W = read_ints()
C = csr_matrix(read_matrix(10))
A = read_matrix(H)

# ダイクストラDFでi→1の各点への最短経路を計算する。
D = dijkstra(C, directed=True)

ans = 0
for a in A:
    for aa in a:
        if abs(aa) == 1:
            continue
        ans += D[aa][1]

print(int(ans))

Submission status: Accepted

Solution code:
def main():
    cost = [[1e10 for j in range(10)]for i in range(10)]
    h,w = map(int,input().split())
    for i in range(10):
        tmp = list(map(int,input().split()))
        for j in range(10):
            if tmp[j] != -1:
                cost[i][j]=tmp[j]
    
    a = list()
    for i in range(h):
        tmp = list(map(int,input().split()))
        a.append(tmp)
    


    for k in range(10):
        for i in range(10):
            for j in range(10):
                cost[i][j] = min(cost[i][k]+cost[k][j],cost[i][j])
    
    ans = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] != -1:
                ans += cost[a[i][j]][1]

    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

H, W = LI()
c = []
for i in range(10):
    c.append(LI())

A = []
for i in range(H):
    A = A + LI()

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

ans = 0
for a in A:
    if a != -1:
        ans += c[a][1]

print(ans)

Submission status: Accepted

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

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

warshall_floyd()

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

Submission status: Accepted

Solution code:
import heapq

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

cost = 0
for i in range(H):
	for j in range(W):
		num = A[i][j]
		if num == -1:
			continue
		else:
			cost += C[num][1]

print(cost)

Submission status: Accepted

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

cost = 0
for a in A:
    for i in a:
        if i > -1:
            cost += dp[i][1]
print(cost)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()
  d=[]
  for _ in range(10):
    d.append(LI())

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

  ans=0
  for _ in range(n):
    l=LI()
    for x in l:
      if x not in (1,-1):
        ans+=d[x][1]

  return ans

# main()
print(main())

Submission status: Accepted

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


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

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

Submission status: Accepted

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

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


d=copy.copy(c)

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

ans=0

for hi in range(h):
    for ahi in a[hi]:
        if(ahi != -1):
            ans+=d[ahi][1]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np
H, W = map(int, input().split())
c = np.array([list(map(int, input().split())) for i in range(10)])
A = [list(map(int,input().split())) for i in range(H)]
d = c[:, 1]
d[1] = 0
ans = 0
for i in range(10):
    if i == 1:
        continue
    q = deque([[i, 0]])
    while len(q) > 0:
        p = q.popleft()
        d[i] = min(d[i], p[1] + c[p[0]][1])
        for j in range(10):
            if j == p[0] or j == 1:
                continue
            if p[1] + c[p[0]][j] < d[i]:
                q.append([j, p[1] + c[p[0]][j]])

for i in range(H):
    for j in range(W):
        if A[i][j] >= 0:
            ans += d[A[i][j]]
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)]
#print(c,a)
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d
n,w = 10,90 #n:頂点数　w:辺の数
edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(10):
    for j in range(10):
        x,y,z = i,j,c[j][i]
        #edge[x].append([z,y]) #有向辺
        edge[y].append([z,x]) #有向辺
ans=[]
for i in range(10):
    ans.append(dijkstra_heap(i)[1])
    #print(dijkstra_heap(i))
#print(ans)
A=0
for i in range(h):
    for j in range(W):
        if a[i][j]>=0:
            A+=ans[a[i][j]]
print(A)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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


def warshall_floyd(dist):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist


cc = warshall_floyd(c)

ans = 0
for a in A:
    if a == -1:
        continue
    ans += cc[a][1]
print(ans)

Submission status: Accepted

Solution code:
def Warshall_Floyd(V, d):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


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

cost_list = Warshall_Floyd(10, cost)
ans = 0

for h in range(H):
    for w in range(W):
        if abs(field[h][w]) == 1:
            continue
        ans += cost_list[field[h][w]][1]

print(ans)

Submission status: Accepted

Solution code:
import heapq


h, w = map(int, input().split())
costs = []
for i in range(10):
    line = list(map(int, input().split()))
    costs.append(line)

mini_cost_to_1_from = [10**4] * 10
mini_cost_to_1_from[1] = 0

for num in range(10):
    if num == 1:
        continue
    seen = [False] * 10
    todo = []
    for to in range(10):
        if num == to:
            continue
        cost = costs[num][to]
        heapq.heappush(todo, [cost, to])

    while todo:
        cost, node = heapq.heappop(todo)
        if node == 1:
            mini_cost_to_1_from[num] = cost
            break

        if seen[node]:
            continue

        seen[node] = cost

        for to in range(10):
            if node == to:
                continue
            if seen[to]:
                continue
            add = costs[node][to]
            heapq.heappush(todo, [cost+add, to])

num_count = [0] * 11
for i in range(h):
    wall = list(map(int, input().split()))
    for num in wall:
        num_count[num] += 1

ans = 0
for num in range(10):
    ans += num_count[num] * mini_cost_to_1_from[num]

print(ans)