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(' '))
tbl = [list(map(int, input().replace("0","100000").split(' '))) for i in range(10)]
tbli = list(zip(*tbl))
cost = [10**5]*10
cost[1]=0
sorttool = [0,1,2,3,4,5,6,7,8,9]
order = list(zip(tbli[1],sorttool))
order.sort()
order.pop()
for i,(c,x) in enumerate(order):
    cost[x] = tbli[1][x]
    if i == 0:
        continue
    for j in range(i):
        cost[x]=min(cost[x],cost[order[j][1]]+tbli[order[j][1]][x])
cost.append(0)
wall = [list(map(int, input().split(' '))) for i in range(h)]
ans =0
for i in range(h):
    for j in range(w):
        ans += cost[wall[i][j]]
print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int, input().split(' '))
tbl = [list(map(int, input().replace("0","100000").split(' '))) for i in range(10)]
tbli = list(zip(*tbl))
cost = [10**5]*10
cost[1]=0
sorttool = [0,1,2,3,4,5,6,7,8,9]
order = list(zip(tbli[1],sorttool))
order.sort()
order.pop()
for i,(c,x) in enumerate(order):
    if i == 0:
        cost[x] = tbli[1][x]
        continue
    for j in range(i):
        cost[x]=min(cost[x],cost[order[j][1]]+tbli[order[j][1]][x])
cost.append(0)
wall = [list(map(int, input().split(' '))) for i in range(h)]
ans =0
for i in range(h):
    for j in range(w):
        ans += cost[wall[i][j]]
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
C = [list(map(int,input().split())) for _ in range(10)]
# warshall-floydで各数字から1に変換するまでの最小魔力を計算
for i in range(10):
    for k in range(10):
        for j in range(10):
            C[i][j] = min(C[i][j], C[i][k]+C[k][j])
# print(C)
powerto1 = {idx: C[idx][1] for idx in range(10)}
#print(powerto1)
ans = 0
for _ in range(H):
    A = list(map(int,input().split()))
    for i in range(W):
        if A[i] != -1:
            ans += powerto1[A[i]]
print(ans)

Submission status: Wrong Answer

Solution code:
#dp=[[0 for j in range(10)] for i in range(10)]
import numpy as np

h,w=map(int,input().split())
dp=np.zeros((10,10))
for i in range(10):
    s=list(map(int,input().split()))
    for j in range(10):
        dp[i][j]=s[j]

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

Submission status: Wrong Answer

Solution code:
import numpy
h,w=map(int,input().split())
c=[[0 for j in range(10)] for i in range(10)]
for i in range(10):
    s=list(map(int,input().split()))
    for j in range(10):
        c[i][j]=s[j]
#print(c)
for i in range(10):
  for j in range(10):
    for k in range(10):
      c[i][j]=min(c[i][k]+c[k][j],c[i][j])
#print(c)
cost=0
for i in range(h):
  t=list(map(int,input().split()))
  for j in range(w):
    if t[j]!=-1 and t[j]!=1.:
      cost+=c[t[j]][1]
print((cost))

Submission status: Wrong Answer

Solution code:
import numpy
h,w=map(int,input().split())
c=numpy.zeros((10,10))
for i in range(10):
  t=list(map(int,input().split()))
  for j in range(10):
    c[i][j]=t[j]
#print(c)
for i in range(10):
  for j in range(10):
    for k in range(10):
      c[i][j]=min(c[i][k]+c[k][j],c[i][j])
#print(c)
cost=0
for i in range(h):
  t=list(map(int,input().split()))
  for j in range(w):
    t[j]
    if t[j]!=-1 and t[j]!=1.:
      cost+=c[t[j]][1]
print(int(cost))

Submission status: Wrong Answer

Solution code:
import numpy
h,w=map(int,input().split())
c=numpy.zeros((10,10))
for i in range(10):
  t=list(map(int,input().split()))
  for j in range(10):
    c[i][j]=t[j]
#print(c)
for i in range(10):
  for j in range(10):
    for k in range(10):
      c[i][j]=min(c[i][k]+c[k][j],c[i][j])
#print(c)
hw=numpy.zeros((h,w))
cost=0
for i in range(h):
  t=list(map(int,input().split()))
  for j in range(w):
    hw[i][j]=t[j]
    if hw[i][j]!=-1. and hw[i][j]!=1.:
      cost+=c[hw[i][j]][1]
print(int(cost))

Submission status: Wrong Answer

Solution code:
import numpy
h,w=map(int,input().split())
c=numpy.zeros((10,10))
for i in range(10):
  t=list(map(int,input().split()))
  for j in range(10):
    c[i][j]=t[j]
#print(c)
for i in range(10):
  for j in range(10):
    for k in range(10):
      c[i][j]=min(c[i][k]+c[k][j],c[i][j])
#print(c)
hw=numpy.zeros((h,w))
cost=0
for i in range(h):
  t=list(map(int,input().split()))
  for j in range(w):
    hw[i][j]=t[j]
    if hw[i][j]!=-1. and hw[i][j]!=1.:
      cost+=c[hw[i][j]][1]
print(cost)

Submission status: Wrong Answer

Solution code:
import numpy
h,w=map(int,input().split())
c=numpy.zeros((10,10))
for i in range(10):
  t=list(map(int,input().split()))
  for j in range(10):
    c[i][j]=t[j]
#print(c)
for k in range(10):
  for i in range(10):
    for j in range(10):
      c[i][j]=min(c[i][k]+c[k][j],c[i][j])
#print(c)
hw=numpy.zeros((h,w))
cost=0
for i in range(h):
  t=list(map(int,input().split()))
  for j in range(w):
    hw[i][j]=t[j]
    if hw[i][j]!=-1 and hw[i][j]!=1:
      cost+=c[hw[i][j]][1]
print(cost)

Submission status: Wrong Answer

Solution code:
import numpy
h,w=map(int,input().split())
c=numpy.zeros((10,10))
for i in range(10):
  t=list(map(int,input().split()))
  for j in range(10):
    c[i][j]=t[j]
#print(c)
for i in range(10):
  for j in range(10):
    for k in range(10):
      c[i][j]=min(c[i][k]+c[k][j],c[i][j])
#print(c)
hw=numpy.zeros((h,w))
cost=0
for i in range(h):
  t=list(map(int,input().split()))
  for j in range(w):
    hw[i][j]=t[j]
    if hw[i][j]!=-1 and hw[i][j]!=1:
      cost+=c[hw[i][j]][1]
print(int(cost))

Submission status: Wrong Answer

Solution code:
import numpy
h,w=map(int,input().split())
c=numpy.zeros((10,10))
for i in range(10):
  t=list(map(int,input().split()))
  for j in range(10):
    c[i][j]=t[j]
#print(c)
for i in range(10):
  for j in range(10):
    for k in range(10):
      c[i][j]=min(c[i][k]+c[k][j],c[i][j])
#print(c)
hw=numpy.zeros((h,w))
cost=0
for i in range(h):
  t=list(map(int,input().split()))
  for j in range(w):
    hw[i][j]=t[j]
    if hw[i][j]!=-1 and hw[i][j]!=1:
      cost+=c[hw[i][j]][1]
print(cost)

Submission status: Wrong Answer

Solution code:
from itertools import permutations as per
h,w = map(int,input().split())
c = [list(map(int,input().split())) for i in range(10)]
ans = 0
mc = [0]*10
for i in range(10):
  mc[i] = c[i][1]
for i in range(1,9):
  for j in per([0,2,3,4,5,6,7,8,9],i):
    cur = 0
    for k in range(1,i):
      cur += c[j[k-1]][j[k]]
    cur += c[j[i-1]][1]
    mc[j[0]] = min(mc[j[0]],cur)
for i in range(h):
  a = list(map(int,input().split()))
  for j in a:
    if j != -1:
      ans += mc[j]
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = (int(i) for i in input().split())

C = []
#C[i][j]
for i in range(10):
  C.append([int(j) for j in input().split()])

for i in range(10):
  for j in range(10):
    new_costs = []
    for k in range(10):
      new_costs.append(C[i][k] + C[k][j])

    C[i][j] = min(min(new_costs),C[i][j])


A_dict = {}
for i in range(H):
  A = [int(i) for i in input().split()]
  for a in A:
    A_dict[a] = A_dict.get(a,0)+1

ans = 0
for A in A_dict.keys():
  if A != -1 and A != 1:
    ans += C[A][1]*A_dict[A]

print(ans)

Submission status: Wrong Answer

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

for _ in range(V):
	C.append(list(map(int, input().split())))
	
for _ in range(H):
	A = list(map(int, input().split()))
	for i in range(W):
		if A[i] != -1:
			ctr[A[i]] += 1
			
for i in range(V):
	for j in range(V):
		for k in range(V):
			if C[i][j] > C[i][k] + C[k][j]:
				C[i][j] = C[i][k] + C[k][j]
				
ans = 0
for i in range(V):
	ans += ctr[i] * C[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):
            x = C[i][k] + C[k][j]
            if x < C[i][j]:
                C[i][j] = x

answer = 0
for x in A:
    for y in x:
        if y > 0:
            answer += C[y][1]
print(answer)

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):
            x = C[i][k] + C[k][j]
            if x < C[i][j]:
                C[i][j] = x

answer = 0
for x in A:
    for y in x:
        if y > 1:
            answer += C[y][1]
print(answer)

Submission status: Wrong Answer

Solution code:
INF = 10**9

def solve():
    # n から 1への最短距離をもとめる
    H,W = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(10)]
    search_table = [[i != j for i in range(10)] for j in range(10)]
    min_distance_n_to_1 = [0]*10
    
    for i in range(0, 10):
        if i == 1: continue
        
        min_distance_node = [INF]*10
        min_distance_node[i] = 0
        search_table = [[i != j for i in range(10)] for j in range(10)]
        dom_stack = [i]
        while dom_stack:
            # if i==8: print(dom_stack)
            dom = dom_stack.pop(0)
            cod_stack = [j for j in range(10) if search_table[dom][j]]
            while cod_stack:
                cod = cod_stack.pop(0)
                search_table[dom][cod] = False
                if min_distance_node[cod] > min_distance_node[dom] + graph[dom][cod]:
                    min_distance_node[cod] = min_distance_node[dom] + graph[dom][cod]
                    #if i == 8: print(dom, cod, min_distance_node[cod])
                    dom_stack.append(cod)
                    
        min_distance_n_to_1[i] = min_distance_node[1]
                    
    # print(min_distance_n_to_1)
    ret = sum(sum(min_distance_n_to_1[int(Aij)] if int(Aij) != -1 else 0 for Aij in input().split()) for _ in range(H))
    print(ret)
    
solve()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
c=[]
for i in range(10):
    c.append(list(map(int,input().split())))
d=[[100000000000]*10 for i in range(10)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            d[i][j]=min(d[i][j],c[i][j],c[i][k]+c[k][j])
ans=0
for i in range(h):
    s=list(map(int,input().split()))
    for j in s:
        if j!=1 and j!=-1:
            ans+=d[j][1]
print(ans)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
INF=float('inf')
cost=[[INF]*10 for _ in range(10)]
for i in range(10):
  tmp=list(map(int,input().split()))
  for j in range(10):
    cost[i][j]=tmp[j]
def warshal_floyd(cost):
  for i in range(10):
    for j in range(10):
      for k in range(10):
        cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])
  return cost
ans=0
min_cost=warshal_floyd(cost)
for i in range(H):
  tmp=list(map(int,input().split()))
  for j in range(W):
    if tmp[j]==-1 or tmp[j]==1:
      pass
    else:
      ans+=min_cost[tmp[j]][1]                 
print(ans)

Submission status: Wrong Answer

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

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

wall = []

for i in range(h):
    wall.append(list(map(int, input().split())))

#solve
#1へのコスト
costone = [(10**3) + 1 for i in range(11)]
#-1, 1はコストがかからないため０で初期化
costone[1] = 0
#-1の処理
costone[10] = 0
#ワーシャルフロイド法を使う
#iは出発、jは経由,
for i in range(10):
    for j in range(10):
        for k in range(10):
            c[i][k] = min(c[i][k], c[i][j] + c[j][k])
#costoneを更新
for i in range(10):
    costone[i] = min(costone[i], c[i][1])
sum = 0
for i in range(h):
    for j in range(w):
        sum += costone[wall[i][j]]
print(sum)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

ans = 0
lst = [0]*11
for i in range(h):
    a = list(map(int,input().split()))
    for j in range(w):
        lst[a[j]+1] += 1

for i in range(2,10):
    ans += lst[i] * dp[i-1][1]
print(ans)

Submission status: Wrong Answer

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

co=[]
c=[0]*10
for i in range(10):
   temp=list(map(int,input().split()))
   co.append(temp)

f=True

for i in range(10):
    for j in range(10):
        temp = []
        for k in range(10):
            if co[i][k] < co[i][j] and co[k][j] < co[i][j]:
                temp.append(co[i][k] + co[k][j])
        if len(temp) >= 1:
            if co[i][j] > min(temp):
                co[i][j] = min(temp)

for i in range(10):
    c[i]=co[i][1]

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

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
c=[]
for i in range(10):
    c.append(list(map(int,input().split())))
d=[[100000000000]*10 for i in range(10)]
for i in range(10):
    for j in range(10):
        for k in range(10):
            d[i][j]=min(d[i][j],c[i][j],c[i][k]+c[k][j])
ans=0
for i in range(h):
    s=list(map(int,input().split()))
    for j in s:
        if j!=1 and j!=-1:
            ans+=d[j][1]
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
B = [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):
            B[i][j] = min(B[i][j],B[i][k]+B[k][j])
G = {i:0 for i in range(-1,10)}
for i in range(H):
    for j in range(W):
        G[A[i][j]] += 1
cnt = 0
for i in range(2,10):
    cnt += G[i]*B[i][1]
print(cnt)

Submission status: Wrong Answer

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

for i in range(10):
    for j in range(10):
        for k in range(10):
            B[i][j] = min(B[i][j],B[i][k]+B[k][j])
G = {i:0 for i in range(-1,10)}
for i in range(H):
    for j in range(W):
        G[A[i][j]] += 1
cnt = 0
for i in range(2,10):
    cnt += G[i]*B[i][1]
print(cnt)

Submission status: Wrong Answer

Solution code:
import copy
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)]
# cost = [[-1]*10 for i in range(10)]
# for j in range(10):
#     cost[j] = [[c[i][j], i] for i in range(10)]
cost = [-1]*10
cost[1] = 0

dp = [[-1]*10 for i in range(10)]
for i in range(10):
    dp[i][i] = 0


def search_cost(i, j, reached, count):
    if dp[i][j] != -1:
        return dp[i][j]
    tmp_list = copy.copy(reached)
    tmp_list.append(i)
    ret = c[i][j]
    count += 1
    if count == 8:
        return ret
    for k in range(10):
        if k == i or k == 1:
            continue
        else:
            tmp = c[i][k] + search_cost(k, j, tmp_list, count)
            ret = min(tmp, ret)
            if ret <= 2:
                break
            #print("i:"+str(i) + "k:" + str(k) + "j:"+str(j) + "=" + str(tmp))

    dp[i][j] = ret
    # for i in range(10):
    #     print(dp[i])
    return ret


for i in range(10):
    if i == 1:
        continue
    else:
        if c[i][1] <= 2:
            dp[i][1] = c[i][1]
            cost[i] = c[i][1]
        else:
            cost[i] = search_cost(i, 1, [], 0)
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] != -1:
            ans += cost[A[i][j]]
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 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])
s=0
for i in range(h):
  for j in range(w):
    if a[i][j]!=-1:
      s+=c[a[i][j]][1]
print(s)

Submission status: 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 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])
s=0
for i in range(h):
  for j in range(w):
    s+=c[a[i][j]][1]
print(s)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
c=[list(map(int,input().split())) for _ in range(10)]
a=[]
for i in range(h):
  t=list(map(int,input().split()))
  for j in t:
    if abs(j)!=1:
      a.append(j)
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])
s=0
for i in a:
  s+=c[i][1]
print(s)

Submission status: Wrong Answer

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

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

#最短距離 (V:頂点数,E:辺数)
#BFS : コスト1 O(E)
#Dijkstra : コスト任意 O(ElogE)
#Floyd Warshall O(V^3) →　今回 V=10 → OK

#「「「Floyd Warshall」」」
#→全点間の重み付きグラフ　経路最小化
#点j→点kに行くまでの最小コスト経路(j→k or j→i→k)
#===========================================================
#iを動かして
#「j→i」のコスト　と　「j→i→kのコスト」　の小さいほうを d[j][k]に採用
#ということを繰り返す
#→直感的には、これでは「2点間コスト」or「3点間コスト」の小さいほうを選んでいるだけっぽいで、
#4点間コスト,5点間コスト,...が最小の場合を考慮していないのでは...
#→実は大丈夫
#===========================================================
#・上の例で,右の経由コストがd[j][k]のコストに採用された場合は(i=i0として)
#「j→i0→k」のコスト と　「j→i0→i1→kのコスト」　の小さいほうを d[j][k]に採用
#これをiを動かして繰り返してコストの最小値を求めるのでn点間最小値も網羅している！！

dist = C[:]
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 i in range(H):
  for j in range(W):
   if(A[i][j] > 0):
     ans += dist[A[i][j]][1]
print(ans)

Submission status: Wrong Answer

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

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

#最短距離 (V:頂点数,E:辺数)
#BFS : コスト1 O(E)
#Dijkstra : コスト任意 O(ElogE)
#Floyd Warshall O(V^3) →　今回 V=10 → OK

#「「「Floyd Warshall」」」
#→全点間の重み付きグラフ　経路最小化
#点j→点kに行くまでの最小コスト経路(j→k or j→i→k)
#===========================================================
#iを動かして
#「j→i」のコスト　と　「j→i→kのコスト」　の小さいほうを d[j][k]に採用
#ということを繰り返す
#→直感的には、これでは「2点間コスト」or「3点間コスト」の小さいほうを選んでいるだけっぽいで、
#4点間コスト,5点間コスト,...が最小の場合を考慮していないのでは...
#→実は大丈夫
#===========================================================
#・上の例で,右の経由コストがd[j][k]のコストに採用された場合は(i=i0として)
#「j→i0→k」のコスト と　「j→i0→i1→kのコスト」　の小さいほうを d[j][k]に採用
#これをiを動かして繰り返してコストの最小値を求めるのでn点間最小値も網羅している！！

dist = C[:]
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 i in range(H):
  for j in range(W):
   if(A[i][j] > 0):
     ans += dist[A[i][j]][1]
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import sys
input = sys.stdin.readline
def inputs():
    return [int(x) for x in input().split()]
H,W = inputs()
c = [inputs() for _ in range(10)]
HW = [inputs() for _ in range(H)]
A = (0,9,8,7,6,5,4,3,2)
B = list(itertools.permutations(A))
N = [c[i][1] for i in range(10)]
for i in B:
    a = i[0]
    ans = 0
    for j in range(1,9):
        ans +=c[i[j-1]][i[j]]
        if N[a]<=ans:
          break
        N[a] = min(ans+c[i[j]][1],N[a])
print(N)        
ans = 0
for i in range(H):
    for j in range(W):
        if HW[i][j]!=-1:
            ans += N[HW[i][j]]
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import sys
input = sys.stdin.readline
def inputs():
    return [int(x) for x in input().split()]
H,W = inputs()
c = [inputs() for _ in range(10)]
HW = [inputs() for _ in range(H)]
A = (0,9,8,7,6,5,4,3,2)
B = list(itertools.permutations(A))
N = [c[i][1] for i in range(10)]

Submission status: Wrong Answer

Solution code:
import itertools
import sys
input = sys.stdin.readline
def inputs():
    return [int(x) for x in input().split()]
H,W = inputs()
c = [inputs() for _ in range(10)]
HW = [inputs() for _ in range(H)]
A = (0,9,8,7,6,5,4,3,2)
B = list(itertools.permutations(A))
N = [c[i][1] for i in range(10)]
ans = 0
for i in B:
    a = i[0]
    ans = 0
    for j in range(1,10):
        ans +=c[i[j-1]][i[j]]
        if N[a]<ans:
          break
        N[a] = min(ans+c[i[j]][1],N[a])
        if N[i[j]]!=10**4+1:
            N[a] = min(ans+N[i[j]],N[a])
            break
ans = 0
for i in range(H):
    for j in range(W):
        if HW[i][j]!=-1:
            ans += N[HW[i][j]]
print(ans)

Submission status: Wrong Answer

Solution code:
z,a,b,c=list(map(int,input().split())),[],0,[]
for i in range(10):
    c.append(list(map(int,input().split())))
for i in range(z[0]):
    a.append(list(map(int,input().split())))
for i in range(10):
    for k in range(10):
        for j in range(10):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])
for i in range(z[0]):
    for j in range(z[1]):
        if a[i][j]!=-1:
            b+=c[a[i][j]][1]
print(b)

Submission status: Wrong Answer

Solution code:
#%%
import copy 

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

d = copy.deepcopy(c)

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


ans = 0
#for i in range(H):
#    for j in range(W):
#        if A[i][j] == 0 or A[i][j] >= 2:
#            ans += d[A[i][j]][1]


for i in A:
    for j in i:
        if j > 1 or j == 0:
            ans += d[j][1]

print(ans)

Submission status: Wrong Answer

Solution code:
import copy 

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

d = copy.deepcopy(c)

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


ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == 0 or A[i][j] >= 2:
            ans += d[A[i][j]][1]

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

H,W = map(int,input().split())
C = [[int(x) for x in input().split()] for _ in range(10)]
num = [0] * 10
for _ in range(H):
    for x in input().split():
        num[int(x)] += 1

que = []
flag = [True]*10
flag[1] = False
cost = [10**10]*10
cost[1] = 0

for i in range(10):
    if flag[i]:
        heapq.heappush(que,[C[i][1],i])

while que:
    a,b = heapq.heappop(que)
    if flag[b]:
        flag[b] = False
        cost[b] = a
        for i in range(10):
            if flag[i]:
                heapq.heappush(que,[C[i][b]+a,i])

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

Submission status: Wrong Answer

Solution code:
import copy

def main():
    H,W = map(int, input().split())
    c = [[int(i) for i in input().split()] for i in range(10)]
    a = [[int(i) for i in input().split()] for i in range(H)]
    d = copy.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 a:
        for j in i:
            if j > 1:
                ans += d[j][1]
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
H,W = map(int, input().split())
c, A = [], []
num = [0] * 10
for _ in range(10):
    ci = list(map(int, input().split()))
    ci[0], ci[1] = ci[1], ci[0]
    c.append(ci)
for _ in range(H):
    A += list(map(int, input().split()))
for i in [0] + list(range(2, 10)):
    num[i] += A.count(i)

c = [[0]] + c[:1] + c[2:]
num[0], num[1] = num[1], num[0]

dp = [[10000 for i in range(10)] for j in range(10)]
dp[1][1] = c[1][0]
for i in range(2, 10):
    dp[i][i] = min(c[i][0], min(c[i][j] + dp[i-1][j] for j in range(i-1, 0, -1)))
    for j in range(1, i):
        dp[i][j] = min(dp[i-1][j], c[j][i] + dp[i][i])

print(sum(dp[9][i] * num[i] for i in range(1,10)))

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
S=[list(map(int, input().split())) for i in range(10)]
l=[None]*10
for i in range(10):
    l[i]=S[i][1]
for i in range(4):
    for j in range(10):
        for k in range(10):
            if l[j]>l[k]+S[j][k]:
                l[j]=l[k]+S[j][k]
l.append(0)
a=0
for i in range(H):
    L=list(map(int,input().split()))
    for j in L:
        a+=l[j]
print(a)

Submission status: Wrong Answer

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

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)

ans=0
for i in range(H):
  A=list(map(int,input().split()))
  for j in A:
    if j>=0:
      ans+=c[j][1]
print(ans)

Submission status: Wrong Answer

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

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)

ans=0
for i in range(H):
  A=list(map(int,input().split()))
  for j in A:
    ans+=c[j][1]
print(ans)

Submission status: Wrong Answer

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

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

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:
import collections

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

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

route={i:10**3 for i in range(10)}
route[1]=0
nonFixPosi=set([0,2,3,4,5,6,7,8,9])
FixPosi=set([1])

for _ in range(11):
  for i in nonFixPosi:
    temp=[route[i]]
    for j in FixPosi:
      temp.append(r[i][j]+route[j])
    route[i]=min(temp)
  
  minKey=[]
  minValue=10**4
  for i in nonFixPosi:
    if route[i]==minValue:
      minKey.append(i)
    elif route[i]<minValue:
      minKey=[i]
      minValue=route[i]
  for item in minKey:
    nonFixPosi.remove(item)
    FixPosi.add(item)
  if len(nonFixPosi)<=0:
    break
    
result=[]
for _ in range(h):
  result+=list(map(int,input().split()))
k=collections.Counter(result)
print(k)
val=0
for i in range(10):
  val+=k[i]*route[i]

print(val)

Submission status: Wrong Answer

Solution code:
import collections

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

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

route={i:10**3 for i in range(10)}
route[1]=0
nonFixPosi=set([0,2,3,4,5,6,7,8,9])
FixPosi=set([1])

for _ in range(11):
  for i in nonFixPosi:
    temp=[route[i]]
    for j in FixPosi:
      temp.append(r[i][j]+route[j])
    route[i]=min(temp)
  
  minKey=[]
  minValue=10*4
  for i in nonFixPosi:
    if route[i]==minValue:
      minKey.append(i)
    elif route[i]<minValue:
      minKey=[i]
      minValue=route[i]
  for item in minKey:
    nonFixPosi.remove(item)
    FixPosi.add(item)
  if len(nonFixPosi)<=0:
    break
  #print(FixPosi)
#print(route)

result=[]
for _ in range(h):
  result+=list(map(int,input().split()))
k=collections.Counter(result)

val=0
for i in range(10):
  val+=k[i]*route[i]

print(val)

Submission status: Wrong Answer

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

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

route={i:10**3 for i in range(10)}
route[1]=0
route[-1]=0
nonFixPosi=set([0,2,3,4,5,6,7,8,9])
FixPosi=set([1])

while len(nonFixPosi)>0:
  for i in nonFixPosi:
    temp=[route[i]]
    for j in FixPosi:
      temp.append(r[i][j]+route[j])
    route[i]=min(temp)
  
  minKey=[]
  minValue=10*4
  for i in nonFixPosi:
    if route[i]==minValue:
      minKey.append(i)
    elif route[i]<minValue:
      minKey=[i]
      minValue=route[i]
  for item in minKey:
    nonFixPosi.remove(item)
    FixPosi.add(item)
  #print(FixPosi)
print(route)

result=0
for _ in range(h):
  k=list(map(int,input().split()))
  for item in k:
    result+=route[item]
    
print(result)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
d = [list(map(int,input().split())) for _ in range(10)]
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])
ans = 0
for _ in range(h):
	for x in map(int,input().split()):
		ans += (x!=-1) * d[x][1]
print(ans)