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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
from heapq import heappush, heappop
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces


H, W = na()
c = [na() for _ in range(10)]
A = [na() for _ in range(H)]
adj = [[] for _ in range(10)]

c = np.array(c)
d = shortest_path(c)
ans = 0
for y in range(H):
    for x in range(W):
        if A[y][x] != -1:
            #print(ans)
            ans += d[A[y][x]][1]
print(int(ans))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
from heapq import heappush, heappop
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces


H, W = na()
c = [na() for _ in range(10)]
A = [na() for _ in range(H)]
adj = [[] for _ in range(10)]



# cost[i][j]: 頂点v_iから頂点v_jへ到達するための辺コストの和
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 y in range(H):
    for x in range(W):
        if A[y][x] != -1:
            #print(ans)
            ans += c[A[y][x]][1]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
H,W = map(int, input().split())
C = []
for i in range(10):
    C.append(list(map(int, input().split())))
INF = float("inf")

def dfs(x):
    memo = [INF]*10
    memo[x] = 0
    hq = [(0,x)]
    heapq.heapify(hq)
    while hq:
        cost,step = heapq.heappop(hq)
        if cost > memo[step]:
            continue
        for j,c in enumerate(C[step]):
            if memo[j] > memo[step] + c:
                memo[j] = memo[step] + c
                heapq.heappush(hq,(memo[j],j))
    return memo[1]

A = [0]*10
for h in range(H):
    for w in map(int, input().split()):
        if w == -1:
            continue
        else:
            A[w] += 1
ans = 0
for number, a in enumerate(A):
    ans += a*dfs(number)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import product

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

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

    ans = sum(C[key][1]*value for key,value in A.items() if key != -1)
    print(ans)

main()

Submission status: Accepted

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

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

Submission status: Accepted

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

H,W = map(int,readline().split())
C = [None] * 10
for i in range(10):
  C[i] = list(map(int,readline().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):
  line = list(map(int,readline().split()))
  for j in range(len(line)):
    if line[j] == -1:
      continue
    ans += C[line[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)]
num = [0]*10
for _ in range(h):
    a = list(map(int, input().split()))
    for i in a:
        if i == -1:
            continue
        num[i] += 1
#a = [list(map(int, input().split())) for _ in range(h)]
#print(num)
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(c)
print(sum(num[x]*c[x][1] for x in range(10)))

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 079 D - Wall

import sys

H, W = map(int, sys.stdin.readline().strip().split())
C = []
for _ in range(10):
    c = list(map(int, sys.stdin.readline().strip().split()))
    C.append(c)

A = []
for h in range(H):
    a = list(map(int, sys.stdin.readline().strip().split()))
    A.append(a)

# コストをワーシャルフロイド
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])

# 必要なコストは、各数字を1 に変化させる部分のみなので
cost = [c[1] for c in C]

# 壁の数字を順番に探索して必要なコストを足していく
ans = 0
for h in range(H):
    for w in range(W):
        # 壁に数字が存在しないとき
        if A[h][w] == -1:
            continue
        ans += cost[A[h][w]]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
h,w = map(int,input().split())
g = Graph()
for i in range(10):
    c = list(map(int,input().split()))
    for j in range(10):
        src,dst,weight = i,j,c[j]
        g.add_edge(src, dst, weight)

ans = 0
for y in range(h):
    tmp = list(map(int,input().split()))
    for x in range(w):
        if tmp[x] != -1 and tmp[x] != 1:
            d = Dijkstra(g, tmp[x])
            ans += d.shortest_distance(1)
print(ans)

Submission status: Accepted

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
#[print(*dist[l]) for l in range(n)]
ans = 0
for i in range(h):
    for j in range(w):
        if wall[i][j]!=-1:
            ans += dist[wall[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)]
d=[0]*10
for _ in range(H):
  for i in list(map(int,input().split())):
    if i>=0: d[i]+=1
r=range(10)
for k in r:
  for i in r:
    for j in r:
      C[i][j]=min(C[i][j],C[i][k]+C[k][j])

print(sum(C[i][1]*d[i] for i in r))

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

H,W=mint()
c=[lint() for _ in range(10)]
A=[lint() for _ in range(H)]
cost=[INF]*10
cost[1]=0
h=[(0,1)]
heapify(h)
while h:
    d,i=heappop(h)
    if d>cost[i]:
        continue
    for j in range(10):
        tmp=c[j][i]+d
        if tmp<cost[j]:
            cost[j]=tmp
            heappush(h,(tmp,j))
ans=0
for i,j in product(range(H),range(W)):
    if A[i][j]>=0:
        ans+=cost[A[i][j]]
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)]
flag = [[1 for _ in range(10)] for _ in range(10)]
for i in range(10):
    que = [[0, i]]
    while que:
        now = heapq.heappop(que)
        flag[i][now[1]] = 0
        for j in range(10):
            if flag[i][j]:
                heapq.heappush(que, [c[i][now[1]]+ c[now[1]][j], j])
                if c[i][now[1]]+c[now[1]][j] < c[i][j]:
                    c[i][j] = c[i][now[1]]+ c[now[1]][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 math
import fractions
#import sys
#input = sys.stdin.readline

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)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

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


h,w = list(map(int, input().split()))

cost = []

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

#print(cost)

INF = 1e9
costs = [[INF for i in range(10)] for j in range(10)]

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

#print(cost)
            
needs=[0 for i in range(10)]

for i in range(h):
    row = list(map(int, input().split()))
    for k in row:
        if(k!=-1): needs[k]+=1

ans = 0
for i in range(10):
    ans += needs[i]*cost[i][1]
    #print(i,cost[i][1])

print(ans)

Submission status: Accepted

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

dist = []
for n in range(N):
    dist.append(list(map(int,input().split())))
dist=[list(x) for x in zip(*dist)]

from collections import deque
start = 1

color = {}
for n in range(N):
    color[n] = -1
    
cost = {}
for n in range(N):
    cost[n] = 10**10
    
parent = {}
for n in range(N):
    parent[n] = -1

cost[start] = 0
S = deque([])
while True:
    mincost = 10**10
    for n in range(N):
        if color[n] != 1 and cost[n] < mincost:
            mincost = cost[n]
            start = n
    
    if mincost == 10**10:
        break
    
    color[start] = 1
    
    for n in range(N):
        if color[n] != 1 and dist[start][n] != -1:
            if cost[start] + dist[start][n] < cost[n]:
                cost[n] = cost[start] + dist[start][n]
                parent[n] = start
                color[n] = 0

cost[-1]=0
ans=0
for h in range(H):
    W = list(map(int,input().split()))
    for w in W:
        ans += cost[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)]
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]
s = 0
for i in range(H):
  a = list(map(int,input().split()))
  for j in range(W):
    if a[j] == -1:
      a[j] = 1
    s += c[a[j]][1]
print(s)

Submission status: Accepted

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

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

#print(cArray)

ans = 0
for i in Aarray:
    for j in i:
        if(j != -1):
            ans += cArray[j][1]

print(ans)

Submission status: Accepted

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

visited = {}
dist = {}
for i in range(10):
    dist[i] = 100000
dist[1] = 0

while len(dist) > 0:
    cur, curDist = sorted(dist.items(), key=lambda x: x[1])[0]
    del dist[cur]
    visited[cur] = curDist

    for i in range(10):
        if i == cur or i in visited:
            continue

        newDist = curDist + c[i][cur]
        dist[i] = min(dist[i], newDist)

cnts = [0] * 10
for _ in range(h):
    a = list(map(int, input().split()))
    for ai in a:
        if ai != -1:
            cnts[ai] += 1

cnt = 0
for i in range(10):
    cnt += cnts[i]*visited[i]

print(cnt)

Submission status: Accepted

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

cost = [99999]*10
cost[1] = 0

def f(n):
    for i in range(10):
        flag = False
        cc = C[i][n]+cost[n]
        if cc < cost[i]:
            flag = True
            cost[i] = cc
            f(i)

f(1)

ans = 0
for _ in range(H):
    for n in map(int, input().split()):
        if n < 0:
            continue
        ans += cost[n]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
c = []
for i in range(10):
  ci = list(map(int,input().split()))
  c.append(ci)
x = [0 for _ in range(10)]
for _ in range(h):
  a = list(map(int,input().split()))
  for ai in a:
    if ai != -1:
      x[ai] += 1
d = [float("inf") for _ in range(10)]
d[1] = 0
done = [False for _ in range(10)]
while sum(done) < 10:
  mni = -1
  mn = float("inf")
  for i in range(10):
    if done[i] == False:
      if mn > d[i]:
        mn = d[i]
        mni = i
  done[mni] = True
  for i in range(10):
    if done[i] == False:
      d[i] = min(d[i],d[mni]+c[i][mni])
ans = 0
for i in range(10):
  ans += x[i]*d[i]
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline
import math
from heapq import heappush, heappop

def solve(h,w,tables,A):
  for i in range(10):
    for j in range(10):
      for k in range(10):
        tables[j][k] = min(tables[j][k], tables[j][i] + tables[i][k])
  cost = 0
  for i in range(h):
    for j in range(w):
      p = A[i][j]
      if p == -1:
        continue
      cost += tables[p][1]
  return cost
  

def main():
  h, w = map(int, input().split(' '))
  tables = []
  for i in range(10):
    tables.append(list(map(int, input().split(' '))))
  A = []
  for _ in range(h):
    A.append(list(map(int, input().split(' '))))
  ans = solve(h, w, tables, A)
  print(ans)
  

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
import math
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]


H, W = zz()
C = []
for i in range(10):
    C.append(zz())
A = []
num_lis = [0]*10
for i in range(H):
    a = zz()
    for a_ in a:
        if (a_ == -1):
            continue
        num_lis[a_] += 1
    A.append(a)
# 1->1, 2->1, 3->1 にするためのコストを計算する
# cost = [0]*10
# for num in range(2, 10):
#     min_cost = C[num][1]
a = floyd_warshall(C)
ans = 0
for i, num in enumerate(num_lis):
    ans += a[i, 1]*num
print(int(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)]


# Warshall–Floyd
def main():
    for k in range(10):
        for i in range(10):
            for j in range(10):
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])

    print(
        sum(
            c[a][1] for column in A for a in column if a >= 0 
        )
    )


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
cost = [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):
            cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
            
ans = 0
for i in range(H):
    for j in range(W):
        now = A[i][j]
        if now != -1:
            ans += cost[now][1]
            
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
inf=10**10
n=10

e = [[inf]*n for _ in range(n)]

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





cost=[inf]*10


def dijkstra(s):
    color=["WHITE"]*n
    d=[inf]*n
    p=[-1]*n
    d[s]=0
    p[s]=-1
    while True:
        mincost =inf
        for i in range(n):
            if color[i] !="BLACK" and d[i] < mincost:
                mincost =d[i]
                u=i
        if mincost ==inf:
            break
        color[u]="BLACK"
        
        for v in range(n):
            if color[v] !="BLACK" and e[u][v] !=inf:
                if d[u] +e[u][v] <d[v]:
                    d[v]=d[u] +e[u][v]
                    p[v]=u
                    color[v] ="GRAY"
    return d[1]
ans=10**10

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



goukei=0
for i in range(10):
    if i!=1:
        ret=dijkstra(i)

        goukei+=ret*T[i]
print(goukei)

Submission status: Accepted

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

table=warshall_floyd(DP)

cnt=[]
ans=0

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


for i in cnt:
  if i==-1:
    continue
  ans+=table[i][1]


print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys, copy, itertools,heapq
input = sys.stdin.readline

h,w = map(int,input().split())
TRANS = [list(map(int,input().split())) for i in range(10)]
A = [list(map(int,input().split())) for i in range(h)]

#print(TRANS)
#print(A)

#warshall_floyd  kijの順番に注意!!
for k in range(10):  #kは中継
  for i in range(10):  # iは始点
    for j in range(10):  #jは目的地
      if (TRANS[i][k] != float('inf')) and (TRANS[i][k] != float('inf')):
        TRANS[i][j] = min(TRANS[i][j],TRANS[i][k] + TRANS[k][j])
#print(TRANS)

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

print(ans)

Submission status: Accepted

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

INF = float('inf')
for k in range(V):
    for i in range(V):
        for j in range(V):
            if cost[i][k]!=INF and cost[k][j]!=INF:
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

out = 0
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        if A[j]==-1:
            continue
        else:
            out += cost[A[j]][1]
print(out)

Submission status: Accepted

Solution code:
N = 10
H, W = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(N)]
A = [list(map(int, input().split())) for _ in range(H)]
for h in range(N):
    for w in range(N):
        if g[h][w] == 0:
            g[h][w] = float('inf')

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

ans = 0
for h in range(H):
    for w in range(W):
        if abs(A[h][w]) != 1:
            ans += g[A[h][w]][1]

print(ans)

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

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

    # Warshall-Floyd
    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 a:
        for j in i:
            if j == -1:
                continue
            else:
                ans += c[j][1]

    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]


def main():
    H, W = MI()
    D = defaultdict(int)
    
    cost = [LI() for i in range(10)]
    
    for i in range(H):
        temp = LI()
        for j in temp:
            if j != -1:
                D[j]+=1

    for i in range(10):
        for j in range(10):
            for k in range(10):
                cost[j][k] = min(cost[j][k], cost[j][i]+cost[i][k])
                
    ans = 0
    
    for key, num in D.items():
        ans += cost[key][1]*num
        
    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Accepted

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


def main():
    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)]
    d = floyd_warshall(csgraph=csr_matrix(c, dtype="i8"), directed=True)
    ans = 0
    for n in itertools.chain.from_iterable(a):
        if n != -1:
            ans += int(d[n][1])
    print(ans)


if __name__ == "__main__":
    main()