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: Wrong Answer

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

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: Wrong Answer

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

magic = [0]*10

cnt = [0]*11

for i in range(h):
    for j in range(w):
        cnt[a[i][j]+1] += 1

d = [[0 for _ in range(10)] for _ in range(10)]

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

ans = 0
for i in range(10):
    ans += cnt[i+1]*(d[i][1])
print(ans)

Submission status: Wrong Answer

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

magic = [0]*10

cnt = [0]*11

for i in range(h):
    for j in range(w):
        cnt[a[i][j]+1] += 1

d = [[0 for _ in range(10)] for _ in range(10)]

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

print(d)
ans = 0
for i in range(10):
    ans += cnt[i+1]*(d[i][1])
print(ans)

Submission status: Wrong Answer

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

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

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

print(answer)

Submission status: Wrong Answer

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, indices=1)
#print(d)
ans = 0
for y in range(H):
    for x in range(W):
        if A[y][x] != -1:
            #print(ans)
            ans += d[A[y][x]]
print(int(ans))

Submission status: Wrong Answer

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]
      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: Wrong Answer

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 A[h][w] > 1:
            ans += g[A[h][w]][1]

print(ans)

Submission status: Wrong Answer

Solution code:
INF=float('inf')
h,w=map(int,input().split())
dist=[[0 for i in range(10)]for j in range(10)]
for i in range(10):
  s=list(map(int,input().split()))
  for j in range(10):
    if i==j:
      continue
    dist[i][j]=s[j]

for i in range(10):
  for j in range(10):
    for k in range(10):
      dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
ans=0
for i in range(h):
  T=list(map(int,input().split()))
  for j in range(w):
    if T[j]==-1:
      continue
    if T[j]==1:
      continue
    ans+=dist[T[j]][1]
print(ans)

Submission status: Wrong Answer

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

import sys
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

INF = float('inf')
H, W = map(int, input().split())

edge = dict()

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

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

res = 0
for h in range(H):
    A = list(map(int, input().split()))
    for a in A:
        if a != -1:
            res += edge[a][1]

print(res)

Submission status: Wrong Answer

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

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

d = copy(data)
def cnt_set(d):
    for i in range(10):
        for j in range(10):
            d[i][1] = min(d[i][1], d[i][j] + d[j][1])
cnt_set(d)
ans = 0

for i in range(h):
    for j in range(w):
        if c[i][j] == -1:
            continue
        ans += d[c[i][j]][1]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline
H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in [0]*10]
A = map(int, read().split())

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

cnt = [0]*10
for a in A:
    if a != -1:
        cnt[a] += 1
ans = 0
for i, c in enumerate(cnt):
    ans += C[i][1] * c
print(ans)

Submission status: Wrong Answer

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


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

al = [list(map(int, input().split())) for _ in range(h)]
ans = 0
for row in al:
    for a in row:
        ans += cl[a][1]
print(ans)

Submission status: Wrong Answer

Solution code:
def warshall_floyd():
    for middle in range(10):
        for start in range(10):
            for end in range(10):
                costs[start][end] = min(costs[start][end], costs[start][middle] + costs[middle][end])


H, W = map(int, input().split())
costs = []

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

warshall_floyd()

print(*costs, sep='\n')
ans = 0
for i in range(H):
    wall = list(map(int, input().split()))
    for num in wall:
        if num != -1:
            ans += costs[num][1]
print(ans)

Submission status: Wrong Answer

Solution code:

def warshall_floyd():
    for start in range(10):
        for end in range(10):
            for middle in range(10):
                c[start][end] = min(c[start][end],c[start][middle] + c[middle][end] )


H, W = map(int, input().split())
c = []

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

warshall_floyd()
ans = 0
for i in range(H):
    wall = list(map(int, input().split()))
    for num in wall:
        if abs(num) != 1:
            ans += c[num][1]
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
c = [[int(i) for i in input().split()] for _ in range(10)]
a = []
for _ in range(h):
    a.extend([int(i) for i in input().split() if i != "-1"])

mins = [c[i][1] for i in range(10)]
for i in range(10):
    for k in range(10):
        mins[i] = min(mins[i], c[i][k] + mins[k])
else:
    print(sum(mins[i] for i in a))

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
c=[list(map(int,input().split())) for _ in range(10)]
dp=[0]*10
for i in range(10):
    dp[i]+=c[i][1]
for _ in range(11):
    for j in range(10):
        for k in range(10):
            dp[j]=min(dp[j],dp[k]+c[j][k])
print(dp)
count=0
for _ in range(h):
    a=list(map(int,input().split()))
    for l in a:
        if l!=-1:
            count+=dp[l]
print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

h,w=map(int,input().split())
c=[]
dic=defaultdict(int)
for _ in range(10): c.append(list(map(int,input().split())))
for _ in range(h):
    temp=list(map(int,input().split()))
    for i in temp: dic[i]+=1
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 item in dic.items():
    if item[0]: ans+=item[1]*c[item[0]][1]
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w = MAP()
c = []
for i in range(10):
    c.append(LIST())
a = []
for i in range(h):
    a.append(LIST())

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

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: Wrong Answer

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

dist=[]
dist.extend(c)
for i in range(10):
  for j in range(10):
    for k in range(10):
      if dist[i][j]>dist[i][k]+dist[k][j]:
        dist[i][j]=dist[i][k]+dist[k][j]
print(sum(dist[a[i][j]][1] for i in range(h) for j in range(w) if a[i][j]>-1))

Submission status: Wrong Answer

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

b3=sorted([[a[i][1],i] for i in range(10)])
c=[b3[i][1] for i in range(10)] 

d={i:10000 for i in range(10)}


for i in c:
  if d[i]!=10000:continue
  x=[a[i][j] for j in range(10)]
  m=x[1]
  for k,v in d.items():
    if v+x[k]<m:m=v+x[k]
  d[i]=m
  
sm=0
for i in range(h):
  s=map(int,input().split())
  for m in s:
    if m!=-1:
      sm+=d[m]
print(sm)

Submission status: Wrong Answer

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

b3=sorted([[a[i][1],i] for i in range(10)])
c=[b3[i][1] for i in range(10)] 

d={i:1001 for i in range(10)}


for i in c:
  if d[i]!=1001:continue
  x=[a[i][j] for j in range(10)]
  m=x[1]
  for k,v in d.items():
    if v+x[k]<m:m=v+x[k]
  d[i]=m
  
sm=0
for i in range(h):
  s=map(int,input().split())
  for m in s:
    if m!=-1:
      sm+=d[m]
print(sm)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from heapq import *
def input(): return sys.stdin.readline().strip()


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

    cost = [10**18] * 10
    cost[1] = 0
    q = [(0, 1)]
    while q:
        c, u = heappop(q)
        if c > cost[u]: continue
        for i in range(10):
            if i == u: continue
            if cost[u] + C[i][u] < cost[i]:
                cost[i] = cost[u] + C[i][u]
                heappush(q, (cost[i], i))
    
    d = defaultdict(int)
    for _ in range(H):
        A = list(map(int, input().split()))
        for a in A: d[a] += 1
    ans = 0
    for i in range(2, 10): ans += cost[i] * d[i]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""

import heapq

INF = 1001

def search_min_c(c_lsit_list):
    min_c_list = [c_lsit_list[i][1] for i in range(10)]
    search_list = list(range(10))
    c_heap = [ [min_c_list[i], i] for i in search_list]
    heapq.heapify(c_heap)
    while c_heap:
        #print(c_heap)
        this_min_c = heapq.heappop(c_heap)
        this_start = this_min_c[1]
        #print(this_start)
        this_c_list = [c_lsit_list[i][this_start] for i in range(10)]
        for pair in c_heap:
            i = pair[1]
            min_c_list[i] = min(
                min_c_list[this_start] + this_c_list[i],
                min_c_list[i]
            )
    return min_c_list

def main():
    H, W = map(int, input().split())
    c_lsit_list = [list(map(int, input().split())) for i in range(10)]
    A_lsit_list = [list(map(int, input().split())) for i in range(H)]

    A_bucket = [0]*10
    for A_list in A_lsit_list:
        for A in A_list:
            if A >= 0:
                A_bucket[A] += 1

    min_c_list = search_min_c(c_lsit_list)

    print(sum([A_bucket[i]*min_c_list[i] for i in range(10)]))
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


def bellman_ford(s):
	d = [float('inf')]*10 # 各頂点への最小コスト
	d[s] = 0 # 自身への距離は0
	for i in range(10):
		update = False # 更新が行われたか
		for x, y, z in g:
			if d[y] > d[x] + z:
				d[y] = d[x] + z
				update = True
		if not update:
 			break
		# 負閉路が存在
		if i == 9:
			return -1
	return d

g = []
for i in range(10):
	for j in range(10):
		x,y,z = j,i,c[i][j]
		g.append([x,y,z])

MINCOST = bellman_ford(1)

sum = 0
for j in range(h):
	for i in range(0,9):
		sum += MINCOST[i+1]*collections.Counter(a[j])[i+1]
print(sum)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
dist = [list(map(int, input().split())) for _ in range(10)]
for i in range(10):
    for j in range(10):
        for k in range(10):
            dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])
ans = 0
for _ in range(H):
    for i in list(map(int, input().split())):
        if i <= 1:
            continue
        ans += dist[i][1]
print(ans)

Submission status: Wrong Answer

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

H, W, *t = map(int, open(0).read().split())
c = np.array(t[:100]).reshape((10, 10))
A = np.array(t[100:])
print(np.sum(shortest_path(c)[:, 1][A[A >= 0]]))

Submission status: Wrong Answer

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

nums = [0 for _ in range(10)]

for i in range(H):
    for num in list(map(int, input().split())):
        if num == -1:
            continue
        else:
            nums[num] += 1


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

ans = 0
# print(costs)
# print(nums)
for i, count in enumerate(nums):
    if i == 0 or count == 0:
        continue
    ans += costs[i][1] * count
print(ans)

Submission status: Wrong Answer

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

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


d=[0]*10
for start in range(10):

    #距離格納配列
    distance=grid[start]

    #確定済み配列
    visited=[0] * 10
    visited[start] = 1
    size = 1

    while size<10:
        min_distance = 10**9
        for i in range(10):
            if visited[i]==0 and distance[i] <min_distance:
                min_distance = distance[i]
                v = i

        visited[v] = 1
        size+=1

        for x in range(10):
            if distance[x] > distance[v] + grid[v][x]:
                distance[x] = distance[v] + grid[v][x]

    d[start]=distance[1]

print(d)


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

print(ans)

Submission status: Wrong Answer

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

H,W = map(int,readline().split())
G = [None] * 10

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

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

ans = 0
for i in range(H):
  line = list(map(int,readline().split()))
  for j in range(W):
    if line[j] == -1:
      continue
    if line[j] == 0:
      continue
    ans += G[line[j]][1]

print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
ans=[float("inf") for i in range(10)]
p=[]
a=[]
for i in range(10):
    p.append(list(map(int,input().split())))
for i in range(h):
    a.append(list(map(int,input().split())))
for i in range(10):
    for j in range(10):
        for k in range(10):
            p[j][k]=min(p[j][i]+p[i][k],p[j][k])
ans=float("inf")
for i in range(10):
    tmp=0
    for j in range(h):
        for k in range(w):
            if a[j][k]!=-1:
                tmp+=p[a[j][k]][i]
    if tmp<ans:
        ans=tmp
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    h, w, *ca = map(int, open(0).read().split())
    it = zip(*[iter(ca[:100])] * 10)
    *c, = map(lambda i: list(i), it)
    a = ca[100:]

    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 a:
        if i < 2:
            continue
        ans += c[i][1]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
C = [tuple(map(int, input().split())) for _ in range(10)]
A = [tuple(map(int, input().split())) for _ in range(h)]
AtoOne = [10 for i in range(10)]

from collections import deque
q = deque([[1, 0]])

while q:
    i, cost = q.popleft()
    if AtoOne[i] > cost:
        AtoOne[i] = cost
    else:
        continue

    for j in range(10):
        if i == j:
            continue
        q.append([j, cost + C[j][i]])

counts = [0] * 10
for i in range(h):
    for j in range(w):
        a = A[i][j]
        if a > -1:
            counts[a] += 1
ans = 0 
for from_i, c in enumerate(counts):
    ans += c * AtoOne[from_i]
print(ans)

Submission status: Wrong Answer

Solution code:
def wa(l):
    for i in range(10):
        for j in range(10):
            for k in range(10):
                l[i][j] = min(l[i][j], l[i][k] + l[k][j])
    return l
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)]
l = wa(c)
ans = 0
for i in a:
    for j in i:
        if j != -1:
            ans += l[j][1]
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
h, w = map(int, input().split())
c = []
for i in range(10):
  s = list(map(int, input().split()))
  c.append(s)

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


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

ans = 0

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

Submission status: Wrong Answer

Solution code:
import copy
import numpy as np

h, w = map(int, input().split())
dp = [list(map(int, input().split())) for _ in range(10)]
arr = np.array([list(map(int, input().split())) for h in range(h)])

# ワーシャルフロイド法で更新がなくなるまで更新
while True:
    prev = copy.deepcopy(dp)
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if i == j:
                    continue
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    if prev != dp:
        break
    prev = dp

arr = arr.flatten()

print(sum([dp[x][1] for x in arr if x != -1 or x != 1]))

Submission status: Wrong Answer

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(3):#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: Wrong Answer

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)]
#print(c)
ans=0
#print(o)
for _ in range(2):#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: Wrong Answer

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)]
#print(c)
ans=0
#print(o)
for _ in range(1):
    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: Wrong Answer

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

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
    minC = deepcopy(C)
    for i in range(10):
        for j in range(10):
            for k in range(10):
                if minC[i][j] + minC[j][k] < minC[i][k]:
                    minC[i][k] = minC[i][j] + minC[j][k]
    
    ans = 0
    for line in A:
        for a in line:
            if a != -1 and a!= 1:
                ans += minC[a][1]
    print(ans)


    
main()

Submission status: Wrong Answer

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: Wrong Answer

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)]
#print(d)
dis=[]
d=warshall_floyd(d)
#print(d)
for i in range(10):
    dis.append(d[i][1])
#print(dis)
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+=dis[lis[i][j]]
print(ans)

Submission status: Wrong Answer

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 i in range(10):
        for j in range(10):
            for k in range(10):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d

h,w=MI()
d=[LI() for i in range(10)]
dis=[]
d=warshall_floyd(d)
for i in range(10):
    dis.append(d[i][1])
#print(dis)
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+=dis[lis[i][j]]
print(ans)