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
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def warshall_floyd(d):
    V = len(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

def resolve():
    H, W = LI()
    c = [LI() for _ in range(10)]
    A = [LI() for _ in range(H)]

    min_cost = warshall_floyd(c)
    # for i in min_cost:
    #     print(i)
    ans = 0
    for i in A:
        for j in i:
            if 0<=j<=9:
                ans += min_cost[j][1]
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import Counter
import heapq

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

Power_map = [0]*10

for i in range(10):
    Q = []
    if i == 1:
        continue
    if Power[i][1] == min(Power[i]):
        Power_map[i] = Power[i][1]
    else:
        to1 = Power[i][1]
        heapq.heappush(Q, (to1, 1))
        for j in range(10):
            if (i == j) or j == 1:
                continue
            elif to1 > Power[i][j]:
                heapq.heappush(Q, (Power[i][j], j))
        while len(Q) > 0:
            Costsum, now = heapq.heappop(Q)
            if now == 1:
                Power_map[i] = Costsum
                break
            for k in range(10):
                if now == k:
                    continue
                elif Costsum + Power[now][k] < to1:
                    heapq.heappush(Q, (Costsum+Power[now][k], k))

Wall = []
for _ in range(H):
    wall = list(map(int, input().split()))
    for __ in range(W):
        if wall[__] >= 0:
            Wall.append(wall[__])
WallC = Counter(Wall)

ans = 0
for i in range(10):
    ans += WallC[i] * Power_map[i]

print(ans)

Submission status: Accepted

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

def dijkstra(S,N,cost):
	d = [float("inf")]*N
	used = [False]*N
	d[S] = 0
	
	while True:
		v = -1
		for i in range(N):
			if (not used[i]) and (v == -1):
				v = i
			elif (not used[i]) and d[i] < d[v]:
				v = i
		if v == -1:
			break
		used[v] = True
		
		for j in range(N):
			d[j] = min(d[j], d[v]+cost[v][j])
	
	return d

min_cost=[0]*10
for i in range(10):
    d=dijkstra(i,10,cost)
    min_cost[i]=d[1]

A=[list(map(int,input().split())) for _ in range(H)]
ans=0
for i in range(H):
    for j in range(W):
        if A[i][j]==-1:
            continue
        else:
            ans+=min_cost[A[i][j]]
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):
    l = list(map(int,input().split()))
    for j in range(10):
        if j != i:
            edges[j][i] = l[j]
costDic = {}
que = [(0,1)]
heapq.heapify(que)
while que:
    cost,now = heapq.heappop(que)
    if now not in costDic:
        costDic[now] = cost
        for nx,c in edges[now].items():
            if nx not in costDic:
                heapq.heappush(que,(cost+c,nx))

ans = 0
for i in range(H):
    wall = list(map(int,input().split()))
    for j in range(W):
        n = wall[j]
        if n != -1:
            ans += costDic[n]

print(ans)

Submission status: Accepted

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

change_costs = [list(map(int, input().split())) for _ in range(10)]
# change_costsは9*9のコスト


for k in range(10):
    for i in range(10):
        for j in range(10):
            # print(k, i, j)
            change_costs[i][j] = min(change_costs[i][j], change_costs[i][k] + change_costs[k][j])
# print(change_costs)
# nums = []
cost = 0
for _ in range(H):
    nums = list(map(int, input().split()))
    for num in nums:
        if num == -1:
            cost += 0
        else:
            cost += change_costs[num][1]
    # nums.append(list(map(int, input().split())))
print(cost)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra

H, W = map(int, input().split())
C = [[int(i) for i in input().split()] for _ in range(10)]
A = []
for _ in range(H):
    A += [int(i) for i in input().split()]
D = dijkstra(C)
D = D[:, 1]
ans = 0
for x in A:
    if abs(x) != 1:
        ans += int(D[x])
print(ans)

Submission status: Accepted

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


def solve(H: int, W: int, c: "List[List[int]]", A: "List[List[int]]"):
    #print(*c, sep='\n')
    for _ in range(10):
        for i in range(10):
            for j in range(10):
                for k in range(10):
                    c[i][j] = min(c[i][j], c[i][k]+c[k][j])
    #print(*c, sep='\n')
    cost = 0
    for a in A:
        for aa in a:
            if aa == -1:
                continue
            cost += c[aa][1]
    return cost


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    c = [[int(next(tokens)) for _ in range(9 - 0 + 1)] for _ in range(9 - 0 + 1)]  # type: "List[List[int]]"
    A = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  # type: "List[List[int]]"
    print(solve(H, W, c, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
import sys
import heapq


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


def dijkstra(start, n_nodes, edge):
    dist = [float("inf")] * n_nodes
    dist[start] = 0
    # 優先度キューの準備
    q = [(dist[start], start)]
    heapq.heapify(q)
    while q:
        # スタートから最も最短距離のものを取り出す
        d, i = heapq.heappop(q)
        # 記録してある情報よりも，取り出した要素に入っている距離情報の方が大きければ
        # 打ち切り．次の要素を取り出す操作に戻る
        if dist[i] < d:
            continue
        # そこから移動できる頂点を探し，最短距離が更新できるものがあれば，
        # 距離を更新して，その頂点への距離と頂点の方法を優先度キューにpush
        for cost, j in edge[i]:
            if dist[j] > dist[i] + cost:
                dist[j] = dist[i] + cost
                heapq.heappush(q, (dist[j], j))
    return dist


sys.setrecursionlimit(20000000)

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


def main():
    H, W = map(int, input().split())
    C = [list(map(int, input().split())) for _ in range(10)]
    edge = [[] for _ in range(10)]
    for i in range(10):
        for j in range(10):
            edge[i].append((C[i][j], j))

    D = [dijkstra(i, 10, edge) for i in range(10)]
    answer = 0
    for _ in range(H):
        A = list(map(int, input().split()))
        for w in range(W):
            if A[w] != -1:
                answer += D[A[w]][1]
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

INF = float("inf")


def warshall_floyd(n, d):
    for k in range(n):
        for i in range(n):
            d_ik = d[i][k]
            if d_ik == INF:
                continue
            for j in range(n):
                if d[i][j] > d_ik + d[k][j]:
                    d[i][j] = d_ik + d[k][j]


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

    warshall_floyd(10, c)

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import heapq


H, w = map(int, input().split())
cost = np.zeros((10, 10), dtype=np.int64)
for i in range(10):
    temp = map(int, input().split())
    for j, x in enumerate(temp):
        cost[j, i] = x
d = np.zeros(10, dtype=np.int64)
h = []
heapq.heappush(h, (0, 1))
while h:
    dx, x = heapq.heappop(h)
    for y in range(10):
        if y in [1, x]:
            continue
        if d[y] == 0 or dx + cost[x, y] < d[y]:
            d[y] = dx + cost[x, y]
            heapq.heappush(h, (d[y], y))
ans = 0
for _ in range(H):
    row = input().split()
    for x in row:
        x = int(x)
        ans += 0 if x == -1 else d[x]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

H,W = map(int,input().split())
dp = [[0]*10 for _ in range(10)]

for i in range(10):
  dp[i] = list(map(int,input().split()))
  
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])
      
el = []
for i in range(H):
  el += list(map(int,input().split()))
  
S=Counter(el)
r = 0
for i in range(10):
  r += S[i]*dp[i][1]
  
print(r)

Submission status: Accepted

Solution code:
from collections import Counter
h,w = map(int,input().split())
n=10
c_input = [list(map(int,input().split())) for i in range(10)]
a_input = [int(j) for i in range(h) for j in input().split() if int(j)!=-1]

a_count = Counter(a_input)

dp=[[float('inf') for i in range(n)]for i in range(n)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            c_input[i][j] = min(c_input[i][j],c_input[i][k]+c_input[k][j])
ans=0
for k,v in a_count.items():
    ans+=c_input[k][1]*v
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra

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

res = 0
for i in range(h):
    for j in map(int, input().split()):
        if j != -1:
            res += dist[j][1]
print(int(res))

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 i == j:continue
            c[i][j] = min(c[i][k] + c[k][j], c[i][j])

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

Submission status: Accepted

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

res = 0
for i in range(h):
    for j in map(int, input().split()):
        if j == -1:
            continue
        else:
            res += cost[j][1]
print(res)

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse.csgraph as csg

from copy import deepcopy

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

d = csg.floyd_warshall(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 i in range(h):
    for j in range(w):
        if a[i][j] != -1:
            ans += d[a[i][j]][1]

print(int(ans))

Submission status: Accepted

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

def main():
    H, W = map(int, readline().rstrip().split())
    C = [list(map(int, readline().rstrip().split())) for _ in range(10)]
    for k in range(10):
        for i in range(10):
            for j in range(10):
                C[i][j] = min(C[i][j], C[i][k] + C[k][j])

    A = [tuple(map(int, readline().rstrip().split())) for _ in range(H)]
    cost = 0
    for h in range(H):
        for w in range(W):
            a = A[h][w]
            if 0 <= a <= 9:
                cost += C[a][1]
    
    print(cost)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from copy import deepcopy

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

d = deepcopy(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 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:
import sys
sys.setrecursionlimit(2147483647)

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

#change[i][j]はiをjに変えるコスト
change=[list(map(int, input().split())) for i in range(10)]
test_case=[list(map(int, input().split())) for i in range(h)]
cost=[0]*10

for i in range(10):
    cost[i]=change[i][1]
#print(cost)
def DEF(start,backed,weight,non_used):
    global cost,change
    #print(backed,non_used)
    if non_used==[]:
        return 0

    for item in non_used:
        if weight+change[backed][item]+change[item][1]<cost[start]:
            cost[start]=weight+change[backed][item]+change[item][1]
        if weight+change[backed][item]<cost[start]:
            non_used2=[]
            for t in non_used:
                if t!=item:
                    non_used2.append(t)

            DEF(start,item,weight+change[backed][item],non_used2)

for item in range(10):
    if item!=1:

        temp=[]
        for i in range(10):
            if item!=i and i!=1:
                temp.append(i)
        #print("######",item,temp)
        DEF(item,item,0,temp)

result=0
for item in test_case:
    for item2 in item:
        if item2!=1 and item2!=-1:
            result+=cost[item2]

print(result)

Submission status: Accepted

Solution code:
from copy import deepcopy
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= deepcopy(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 i in range(H):
  for j in range(W):
    if A[i][j]==-1 or A[i][j]==1:
      pass
    else:
      ans += d[A[i][j]][1]
      
print(ans)

Submission status: Accepted

Solution code:
# d : 隣接行列
# n : n * n
def warshall_floyd(n, 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])
                #print(d)
    return d
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)]
c = warshall_floyd(10, c)
import collections
dic = collections.defaultdict(int)
for i in range(h):
    for j in range(w):
        dic[a[i][j]] += 1
ans = 0
for key in dic.keys():
    if key != -1:
        ans += c[key][1] * dic[key]
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)]
def warshall_floyd(n, 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
dic = {}
for i in range(h):
    for j in range(w):
        if a[i][j] not in dic:
            dic[a[i][j]] = 1
        else:
            dic[a[i][j]] += 1
          
c = warshall_floyd(10, d=c)          

ans = 0
for i in dic.keys():
    if i != -1 and i != 1:
        ans += c[i][1] * dic[i]
print(ans)

Submission status: Accepted

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

def solve():
    d = []
    for i in range(10): #ひとまず枝があるペアは枝の長さをセット
        d.append(list(map(int, input().split())))

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

    #三重ループ
    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]
    return ans
print(solve())

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))

# rstrip().decode('utf-8')

#import numpy as np
import heapq

def main():
	h,w=MI()
	
	G=[]
	for _ in range(10):
		c=LI()
		G.append(c)
	#print(G)
	
	for k in range(10):
		for i in range(10):
			for j in range(10):
				G[i][j]=min(G[i][j],G[i][k]+G[k][j])
	
	ans=0
	for _ in range(h):
		row=LI()
		for val in row:
			if abs(val)!=1:
				ans+=G[val][1]
	print(ans)
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
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


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
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

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
h, w = map(int, input().split())        
c = [list(map(int, input().split())) for i in range(10)]
cnt = [0 for i in range(10)]
for i in range(h):
    a = list(map(int, input().split()))
    for j in a:
        if j != -1:
            cnt[j] += 1
d = warshall_floyd(c, 10)
ans = 0
for i in range(10):
    ans += cnt[i] * c[i][1]
print(ans)

Submission status: Accepted

Solution code:
def dijkstra(start_node, num_nodes, cost_dict):
    import heapq

    initial_nodes = cost_dict[start_node]
    min_costs = {start_node : 0}
    available_nodes = initial_nodes
    done_nodes = set([start_node])
    heapq.heapify(available_nodes)
    
    # Loop until all nodes are searhced
    while len(available_nodes) > 0:
        (min_cost, dest_node) = heapq.heappop(available_nodes)
        if(dest_node in done_nodes):
            continue
        min_costs[dest_node] = min_cost
        done_nodes.add(dest_node)
        # New available nodes
        for new_node in cost_dict[dest_node]:
            new_node_cost = new_node[0] + min_cost
            new_node_dest = new_node[1]
            if(new_node_dest in done_nodes):
                continue
            heapq.heappush(available_nodes, (new_node_cost, new_node_dest))
    return min_costs

def main():
    import copy
    H, W = map(int, input().split())
    cost_dict_org={i:[] for i in range(10)}
    for i in range(10):
        c_list = list(map(int, input().split()))
        for j in range(10):
            cost_dict_org[i].append((c_list[j], j))
    
    min_cost_dict = {}
    

    for i in range(10):
        cost_dict = copy.deepcopy(cost_dict_org)
        min_dict = dijkstra(i, 10, cost_dict)
        min_cost_dict[i]=min_dict
    
    A = []

    answer = 0
    for h in range(H):
        a_row = list(map(int, input().split()))
        for a in a_row:
            if(a == 1 or a == -1):
                continue
            else:
                answer += min_cost_dict[a][1]
    print(answer)


main()

Submission status: Accepted

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

INF = float("inf")


def warshall_floyd(n, d):
    for k in range(n):
        for i in range(n):
            d_ik = d[i][k]
            # if d_ik == INF:
            #     continue
            for j in range(n):
                if d[i][j] > d_ik + d[k][j]:
                    d[i][j] = d_ik + d[k][j]


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

    warshall_floyd(10, c)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

INF = float("inf")


def warshall_floyd(n, d):
    for k in range(n):
        for i in range(n):
            d_ik = d[i][k]
            if d_ik == INF:
                continue
            for j in range(n):
                if d[i][j] > d_ik + d[k][j]:
                    d[i][j] = d_ik + d[k][j]


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

    warshall_floyd(10, c)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

for i in range(H):
    for j in range(W):
        a=A[i][j]
        if a>=0:
            res+=c[a][1]

print(res)

Submission status: Accepted

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

INF = float("inf")


def f(c, pos, unused, sum_c):
    if pos == 1:
        return sum_c
    ret = INF
    l = unused[:]
    l.remove(pos)
    for next_n in l:
        res = f(c, next_n, l, sum_c + c[pos][next_n])
        if res < ret:
            ret = res
    return ret


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

    c_min = [0] * 10
    for i in range(10):
        c_min[i] = f(c, i, list(range(10)), 0)

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


if __name__ == "__main__":
    main()

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 i == j:continue
            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):
        temp = a[i][j]
        if temp == -1:continue
        cost += c[temp][1]
print(cost)

Submission status: Accepted

Solution code:
from collections import Counter

def main():
    h, w = map(int, input().split())
    c = [[int(i) for i in input().split()] for _ in range(10)]
    for k in range(10):
        for i in range(10):
            for j in range(10):
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])
    print(sum(c[k][1] * v for k, v in Counter(sum([[int(i) for i in input().split() if i != "-1"] for _ in range(h)], [])).items()))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


# 数字->数字に変えるcostを更新する（ワーシャルフロイド法）
for k in range(10):
    for i in range(10):
        for j in range(10):
            Cs[i][j] = min(Cs[i][j], Cs[i][k] + Cs[k][j])

# 解答
count = 0
for i in range(H):
    for j in range(W):
        if As[i][j] >= 0:
            #print('number=', As[i][j], 'cost=', Cs[As[i][j]][1])
            count += Cs[As[i][j]][1]

print(count)