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:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

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

A = []
for i in range(H):
    temp = LI()
    A.append(temp)

def WF(E,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                E[i][j] = min(E[i][j],E[i][k]+E[k][j])
    return E

E = [[float('inf')]*10 for _ in range(10)]
for i in range(10):
    E[i][i] = 0         #自分との距離は0にしておく
for i in range(10):
    for j in range(10):
        E[i][j] = c[i][j]

dist = WF(E,10)

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

print(ans)

Submission status: Accepted

Solution code:
class WarshallFloyd:
    def __init__(self,V,inf):
        self.V=V
        self.inf=inf
        self.G=[[inf]*V for _ in range(V)]
        for i in range(V):
            self.G[i][i]=0

    def add(self,u,v,cost):
        self.G[u][v]=min(self.G[u][v],cost)

    def shortest_path(self):
        for k in range(self.V):
            for i in range(self.V):
                for j in range(self.V):
                    self.G[i][j]=min(self.G[i][j],self.G[i][k]+self.G[k][j])
        return self.G

    def exist_negative_loop(self):
        for i in range(self.V):
            if self.G[i][i]<0:
                return True
        return False

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    inf=10**9
    h,w=map(int,readline().split())
    c=[list(map(int,readline().split())) for _ in range(10)]
    a=[list(map(int,readline().split())) for _ in range(h)]
    wf=WarshallFloyd(10,inf)
    for i in range(10):
        for j in range(10):
            if i==j: pass
            else: wf.add(i,j,c[i][j])

    tmp=wf.shortest_path()
    to_one=[tmp[i][1] for i in range(10)]

    ans=0
    for i in range(h):
        for j in range(w):
            if a[i][j]==-1: pass
            else:
                ans+=to_one[a[i][j]]

    print(ans)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
import numpy as np

H, W = map(int, input().split())
C = [list(map(int, input().split())) for i in range(10)]
cost = np.r_[dijkstra(C)[:, 1], 0].astype(int)

A = np.array([list(map(int, input().split())) for i in range(H)])
print(cost[A].sum())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

H,W = IL()
C = ILL(10)
Wall = ILL(H)
class WarshallFloyd():
  def __init__(self, N):
    self.N = N
    self.d = [[float("inf") for i in range(N)] for i in range(N)]

  def add(self, u, v, c, directed=False):
    if directed is False:
      self.d[u][v] = c
      self.d[v][u] = c
    else:
      self.d[u][v] = c

  def WarshallFloyd_search(self):
    for k in range(self.N):
      for i in range(self.N):
        for j in range(self.N):
          self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
    hasNegativeCycle = False
    for i in range(self.N):
      if self.d[i][i] < 0:
        hasNegativeCycle = True
        break
    for i in range(self.N):
      self.d[i][i] = 0
    return hasNegativeCycle, self.d
  
graph = WarshallFloyd(10)
for i in range(10):
  for j  in range(10):
    graph.add(i,j,C[i][j],directed=True)
f,d = graph.WarshallFloyd_search()

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

Submission status: Accepted

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):
            path[j][k] = min(path[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 or A[j] == 1:
            continue
        else:
            ans += path[A[j]][1]
print(ans)

Submission status: Accepted

Solution code:
import heapq
H, W = map(int, input().split())
edges = [[] for _ in range(10)]
for i in range(10):
    e_list = list(map(int, input().split()))
    for j in range(10):
        if j == i:
            continue
        edges[i].append([j, e_list[j]])
A = []
for i in range(H):
    A.append(list(map(int, input().split())))

def dijkstra(edges, num_v, start):
    dist = [float('inf')] * num_v
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])

    while len(q) > 0:
        _, u = heapq.heappop(q)
        for edge in edges[u]:
            if dist[edge[0]] > dist[u] + edge[1]:
                dist[edge[0]] = dist[u] + edge[1]
                heapq.heappush(q, [dist[u] + edge[1], edge[0]])
    return dist
ans = 0
root_list = [0] * 10
for i in range(10):
    if i == 1:
        continue
    root_list[i] = dijkstra(edges, 10, i)[1]
for a_line in A:
    for a in a_line:
        if a == -1 or a == 1:
            continue
        ans += root_list[a]

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
h, w = map(int, input().split())
c = [[] for _ in range(10)]
cnt = [0] * 10
for i in range(10):
    c[i] = list(map(int, input().split()))
a = [[] for _ in range(h)]
for i in range(h):
    a[i] = list(map(int, input().split()))
    for j in range(10):
        cnt[j] += a[i].count(j)
visit = [0] * 10
val = [c[i][1] for i in range(10)]
visit[1] = 1
pos = 1
while sum(visit) < 10:
    tmp = 10 ** 5  # INF
    for i in range(10):
        if not visit[i]:
            val[i] = min(val[i], val[pos] + c[i][pos])
            if tmp > val[i]:
                # pos = i#ここを更新したらあかんやん。。。
                next_pos = i
                tmp = val[i]
    pos = next_pos
    visit[pos] = 1
ans = 0
# print(val)
for i in range(10):
    ans += val[i] * cnt[i]
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
cost = []
INF = 10**9
for i in range(10):
  cost.append(list(map(int, input().split())))
for i in range(10):
  cost[i][i] = INF
A = []
for i in range(H):
  A.append(list(map(int, input().split())))

d = [INF]*10
used = [False] *10
V = 10
def shortest_path(start = 1):#隣接行列の場合のダイクストラ法
  d[start] = 0
  while True:
    v = -1
    for u in range(V):
      if (not used[u]) and (v == -1 or d[u] < d[v]):v = u
    if v == -1:break
    used[v] = True
    for u in range(V):
      d[u] = min(d[u], d[v] + cost[u][v])
  
def main():
  shortest_path()
  ans = 0
  for i in range(H):
    for j in range(W):
      if A[i][j] != -1:
        ans += d[A[i][j]]
  print(ans)
if __name__ == "__main__":
  main()

Submission status: Accepted

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

import numpy as np

inputs = []

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

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: 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)]
o=[c[i][1] for i in range(10)]#初期状態として各iから直接1にいく場合の魔力を入れる
#print(c)
ans=0
#print(o)
for _ in range(10):#o[i],o[j]は更新されていくので、最低10回は回す（最長移動距離が10のため）
    for i in range(10):
        for j in range(10):
            o[i]=min(o[i],c[i][j]+o[j])#例えば4から1に行く場合、直接行くと9かかるが、4→9→1といくと4で済む。
    #print(o)
    
for s in range(h):
    for t in range(w):
        if A[s][t]!=-1:
            ans+=o[A[s][t]]
print(ans)

Submission status: Accepted

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

# ワーシャルフロイド法
# 全頂点間最短路
# d[i][j]は2頂点間i, j間の移動コストを格納, Mは頂点数

from scipy.sparse.csgraph import floyd_warshall
from collections import Counter

def main():
    H, W = map(int,input().split())
    d = [list(map(int,input().split())) for _ in range(10)]
    fw=floyd_warshall(d)
    p = []
    for i in range(H):
        p+=list(map(int,input().split()))
    p = Counter(p)
    ret = 0
    for i in range(10):
        if i==1: continue
        ret += p[i]*fw[i][1]
    print(int(ret))


if __name__ == '__main__':
    main()

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)]
o=[c[i][1] for i in range(10)]#初期状態として各iから直接1にいく場合の魔力を入れる
#print(c)
ans=0
#print(o)
for _ in range(5):#o[i],o[j]は更新されていくので、最低10回は回す（最長移動距離が10のため）
    for i in range(10):
        for j in range(10):
            o[i]=min(o[i],c[i][j]+o[j])#例えば4から1に行く場合、直接行くと9かかるが、4→9→1といくと4で済む。
    #print(o)
    
for s in range(h):
    for t in range(w):
        if A[s][t]!=-1:
            ans+=o[A[s][t]]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    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
    for m in range(10):
        for f in range(10):
            for t in range(10):
                C[f][t] = min(C[f][t], C[f][m] + C[m][t])


    
    ans = 0
    for line in A:
        for a in line:
            if abs(a) != 1:
                ans += C[a][1]
    print(ans)


    
main()

Submission status: Accepted

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

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])
count = [0]*10
for i in range(H):
    tmp = list(map(int, input().split()))
    for t in tmp:
        if t != -1:
            count[t] += 1

ans = 0
for i in range(10):
    ans += count[i] * c[i][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)]
INF = 10**10
d = [[c[i][j] for j in range(10)] 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])

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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
INF = 10**9
costs = [list(map(int, input().split())) for _ in range(10)]
for k in range(10):
    for j in range(10):
        for i in range(10):
            if costs[i][j] > costs[i][k] + costs[k][j]:
                costs[i][j] = costs[i][k] + costs[k][j]
opt_costs = [costs[i][1] for i in range(10)]
ans = 0
for _ in range(h):
    a = list(map(int, input().split()))
    for v in a:
        if v > -1:
            ans += opt_costs[v]
print(ans)

Submission status: Accepted

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


def main():
    H, W = map(int, input().split())
    INF = 10**12
    c = [None for _ in range(10)]
    for i in range(10):
        c[i] = list(map(int, input().split()))

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

A = []
for _ in range(H):
    A += 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])

from collections import Counter
Co = Counter(A)
ans = 0
for a, c in Co.most_common():
    if a==-1 or a==1:
        continue
    ans += C[a][1]*c
print(ans)

Submission status: Accepted

Solution code:
import heapq


def min_mp_to_one(C):
    # calculate minimum magical power to change number to 1
    INF = 10**4
    min_mp = [INF for _ in range(len(C))]
    min_mp[1] = 0
    frontier = [(0, 1)]  # (mp, number)
    while len(frontier) > 0:
        mp, n = heapq.heappop(frontier)
        for next_n in range(len(C)):
            if next_n == n:
                continue
            if min_mp[next_n] > mp + C[next_n][n]:
                # use C[next_n][n] (not C[n][next_n])
                # because this procedure starts from 1 (opposite direction)
                min_mp[next_n] = mp + C[next_n][n]
                heapq.heappush(frontier, (min_mp[next_n], next_n))
    return min_mp


def main():
    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)]
    min_mp = min_mp_to_one(C)
    ans = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == -1:
                continue
            ans += min_mp[A[h][w]]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

INF = 10 ** 7

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

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

    def dijkstra(s):
        que = list()
        heapq.heapify(que)
        cost = [INF] * (10)
        cost[s] = 0
        heapq.heappush(que, [cost[s], s])

        while que:
            v = heapq.heappop(que)
            if cost[v[1]] < v[0]: continue
            for i in range(10):
                if cost[i] > cost[v[1]] + C[v[1]][i]:
                    cost[i] = cost[v[1]] + C[v[1]][i]
                    heapq.heappush(que, [cost[i], i])
        return cost[1]

    mc = [INF] * 10
    for i in range(10): mc[i] = dijkstra(i)
    output = 0
    for i in range(H):
         for j in range(W):
             if A[i][j] == -1: continue
             output += mc[A[i][j]]
    print(output)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# ABC 79
def main():
    MAX = 10**6
    H,W = list(map(int, input().split()))
    costs = [list(map(int, input().split())) for i in range(10)]
    to_ones = [MAX] * 10
    to_ones[1] = 0
    visited = set([1])
    un_visited = set([i for i in range(10)])
    un_visited.remove(1)

    while len(un_visited) > 0:
        target = 0
        min_val = MAX
        for i in visited:
            for j in un_visited:
                if costs[j][i] < min_val:
                    min_val = costs[j][i]
                    target = j

        visited.add(target)
        un_visited.remove(target)
        to_ones[target] = min_val

        for x in un_visited:
            costs[x][target] += min_val
        
    A_cnts = [0] * 11 # -1 -> 10

    for i in range(H):
        A = list(map(int, input().split()))
        for a in A:
            A_cnts[a] += 1
    
    res = 0
    for i in range(10):
        if i == 1:
            continue
        res += A_cnts[i] * to_ones[i]

    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
h, w = map(int, input().split())
c = []
for _ in range(10):
    c.append(list(map(int, input().split())))
a = [0]*10
for _ in range(h):
    for i in map(int, input().split()):
        if i<0:
            continue
        a[i] += 1
INF = 10**10
q = list(range(10))
dist = [INF]*10
dist[1] = 0
while q:
    mi = INF
    for i in q:
        if dist[i]<mi:
            mi = dist[i]
            mi_ind = i
    node = mi_ind
    q.remove(mi_ind)
    for i in range(10):
        if dist[node]+c[i][node] < dist[i]:
            dist[i] = dist[node]+c[i][node]

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

Submission status: Accepted

Solution code:
from itertools import permutations
h, w = map(int, input().split())
c = []
for _ in range(10):
    c.append(list(map(int, input().split())))
a = [0]*10
for _ in range(h):
    for i in map(int, input().split()):
        if i<0:
            continue
        a[i] += 1
ans = 0    
for i in range(10):
    if i==1 or a[i]==0:
        continue
    mi = c[i][1]
    li = [k for k in range(10) if k!=1 and k!=i]
    for j in range(1, 9):
        for p in permutations(li, j):
            pre = i
            tmp = 0
            for now in p:
                tmp += c[pre][now]
                pre = now
            tmp += c[pre][1]
            if tmp < mi:
                mi = tmp
    ans += mi*a[i]
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)]

# 0~9の数値を頂点として、Bellman-fordで最短経路を求める
INF = 10**10
dist = [[c[i][j] for j in range(10)] for i in range(10)]
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])

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

print(ans)

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i):
            is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
## libs ##
from itertools import accumulate as acc
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left

#======================================================#

def main():
    h,w = MII()
    d = [MII() for i in range(10)]
    wall = []
    for i in range(h):
        wall += MII()
    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 = sum([d[w][1] for w in wall if w != -1])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

def warshall_floyd(d):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d
h,w=MI()
d=[LI() for i in range(10)]
d=warshall_floyd(d)
lis=[LI() for i in range(h)]
ans=0
for i in range(h):
    for j in range(w):
        if lis[i][j]>=0:
            ans+=d[lis[i][j]][1]
print(ans)

Submission status: Accepted

Solution code:
h, w = list(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][i] + power[i][k], power[j][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:
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 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 h in range(H):
    for w in range(W):
        if A[h][w]!=-1 and A[h][w]!=1:
            ans+=c[A[h][w]][1]
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall

h,w=map(int,input().split(' '))
cost=[list(map(int,input().split(' '))) for _ in range(10)]
dist=floyd_warshall(cost)
cost=[dist[i][1] for i in range(10)]

total=0
for _ in range(h):
    wall=list(map(int,input().split(' ')))
    for num in wall:
        if num==-1 or num==1:
            continue
        total+=cost[num]
print(int(total))

Submission status: Accepted

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

H, W = MAP()
c = [LIST() for _ in range(10)]
A = [LIST() for _ in range(H)]

#ワーシャルフロイド法  注意 PyPy非対応!!!!
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

graph = csr_matrix(c) #隣接行列からcsr行列をつくる
c = floyd_warshall(graph, directed=True) #無向の場合directed=True
#dist_matrixの中身はfloatになっているので注意！
	

#for i in range(10):
#	print(c[i])

import numpy as np
#距離
def distance(p1, p2):
	p1 = np.array(p1)
	p2 = np.array(p2) 
	return np.linalg.norm(p1-p2)
	

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

print(int(ans))