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:

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

    # i, j間の最短距離を求める
    dist = {(i, j): float('inf') for i in range(10) for j in range(10)}
    for i in range(10):
        for j in range(10):
            dist[(i, j)] = costs[i][j]

    for i in range(10):
        for j in range(10):
            if i == j:
                continue
            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):
        for j in range(w):
            if a[i][j] < 0:
                continue    
            ans += dist[(a[i][j], 1)]
    print(ans)

    
submit()

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

def func(num, goto, ignore):
    if num == goto:
        return 0
    res = []
    for i in range(10):
        if i in ignore:
            continue
        ignore3 = deepcopy(ignore)
        ignore3.append(i)
        plus = func(i, goto, ignore3) if d[i][goto] == -1 else d[i][goto]
        d[i][goto] = plus
        tmp = c[num][i] + plus
        res.append(tmp)
    return min(res)
    '''
    if num == goto:
        return 0
    ignore.append(num)
    mn = inf
    retnum = 0
    for j in range(10):
        if j in ignore:
            continue
        if c[num][j] < mn:
            mn = c[num][j]
            retnum = j
    res = func(retnum, goto, ignore) + mn
    return res
    '''

h, w = MAP()
c = [LIST() for _ in range(10)]
d = [[-1 for _ in range(10)] for _ in range(10)]
a = [LIST() for _ in range(h)]
for i in range(10):
    for j in range(10):
        if i == 1:
            continue
        res = func(i, j, [i])
        d[i][j] = min(c[i][j], res)
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == -1 or a[i][j] == 1:
            continue
        ans += d[a[i][j]][1]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

def func(num, goto, ignore):
    if num == goto:
        return 0
    mn = inf
    retnum = 0
    for j in range(10):
        if j == num or j in ignore:
            continue
        if c[num][j] < mn:
            mn = c[num][j]
            retnum = j
    ignore.append(num)
    res = func(retnum, goto, ignore) + mn
    return res

h, w = MAP()
c = [LIST() for _ in range(10)]
a = [LIST() for _ in range(h)]
for i in range(10):
    for j in range(10):
        c[i][j] = min(c[i][j], func(i, j, []))
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == -1 or a[i][j] == 1:
            continue
        ans += c[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.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 k in range(10):
        for j in range(10):
            C[i][j]=min(C[i][j],C[i][k]+C[k][j])
cnt=0
for i in range(h):
    for j in range(w):
        if A[i][j]==-1 or A[i][j]==1:
            continue
        cnt+=C[A[i][j]][1]
print(cnt)

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

for i in range(10):
    for j in range(10):
        for k in range(10):
            c[j][k] = min(c[j][k],c[j][i]+c[i][k])
ans = 0
for i in range(h):
    for j in range(w):
        if A[i][j] > 0:
            ans += c[A[i][j]][1]
print(ans)

Submission status: Wrong Answer

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

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

def wf(table):
    from itertools import product
    for i, j, k in product(range(len(table)), repeat=3):
        table[i][j] = min(table[i][j], table[i][k] + table[k][j])

    return table

table = wf(table)

ans = 0
for _ in range(h):
    for i in map(int, input().split()):
        if i != -1:
            ans += table[i][1]

print(ans)

Submission status: Wrong Answer

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

dp = [-1] * 10
for i in range(10):
    dp[i] = list(map(int,input().split()))

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

ans = 0
for _ in range(h):
    a = list(map(int,input().split()))
    for i in range(w):
        if a[i] == 1 or a[i] == -1:
            pass

        else:
            ans += dp[a[i]][1]

print(ans)

Submission status: Wrong Answer

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

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

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

ans = 0
for _ in range(h):
    a = list(map(int,input().split()))
    for i in range(w):
        if a[i] == 1 or a[i] == -1:
            continue

        else:
            ans += dp[a[i]][1]

print(ans)

Submission status: Wrong Answer

Solution code:
def calc_mp(C, d):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if k == 0:
                    d[i][j][k] = C[i][j]
                else:
                    d[i][j][k] = min(d[i][j][k-1], d[i][k][k-1] + d[k][j][k-1])

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

    d = [[[1000*10+1 for i in range(10)] for i in range(10)] for i in range(10)]
    calc_mp(C, d)

    # print(d)
    ans = 0
    for h in range(H):
        for w in range(W):
            a = A[h][w]
            if a != -1 and a != 1:
                ans += d[a][1][9]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def calc_mp(C, d):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if k == 0:
                    d[i][j][k] = C[i][j]
                else:
                    d[i][j][k] = min(d[i][j][k-1], d[i][k][k-1] + d[k][j][k-1])

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

    d = [[[1001 for i in range(10)] for i in range(10)] for i in range(10)]
    calc_mp(C, d)

    # print(d)
    ans = 0
    for h in range(H):
        for w in range(W):
            a = A[h][w]
            if a != -1 and a != 1:
                ans += d[a][1][9]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def calc_mp(C, d):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if k == 0:
                    d[i][j][k] = C[i][j]
                else:
                    d[i][j][k] = min(d[i][j][k-1], d[i][k][k-1] + d[k][j][k-1])

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

    d = [[[0 for i in range(10)] for i in range(10)] for i in range(10)]
    calc_mp(C, d)

    # print(d)
    ans = 0
    for h in range(H):
        for w in range(W):
            a = A[h][w]
            if a != -1 and a != 1:
                ans += d[a][1][9]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def calc_mp(C, d):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if k == 0:
                    d[i][j][k] = C[i][j]
                else:
                    d[i][j][k] = min(d[i][j][k-1], d[i][k][k-1] + d[k][j][k-1])

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

    d = [[[0 for i in range(10)] for i in range(10)] for i in range(10)]
    calc_mp(C, d)

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
C = []
for _ in range(10):
  List = list(map(int,input().split()))
  C.append(List)
Wall = []
for _ in range(H):
  List = list(map(int,input().split()))
  Wall.append(List)
for i in range(10):
  for j in range(10):
    for k in range(10):
      if i != j:
        C[i][j] = min(C[i][j],C[i][k]+C[k][j])
      else:
        C[i][j] = 0
Answer = 0
for line in Wall:
  for item in line:
    if item!= -1:
      Answer += C[item][1]
print(Answer)

Submission status: Wrong Answer

Solution code:
h,w = map(int, input().split())
c = []
for i in range(10):
  arr = list(map(int, input().split()))
  c.append(arr)
  
a = []
for i in range(h):
  arr = list(map(int, input().split()))
  a.append(arr)
  
for i in range(10):
  arr = c[i]
  kakutei = [False] * 10
  kakutei[i] = True

  kakutei_num = 1
  while kakutei_num != 10:
    min_num = 11
    index = -1
    for j in range(10):
      if not kakutei[j] and min_num > arr[j]:
        min_num = min(min_num, arr[j])
        index = j
      
    kakutei[index] = True
    kakutei_num += 1
    for j in range(10):
      c[i][j] = min(c[i][j], c[i][index] + c[index][j])
      
ans = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == -1:
      continue
    
    n = a[i][j]
    ans += c[n][1]
'''    
for i in range(len(c)):
  print(c[i])
'''
print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int, input().split())
c = []
for i in range(10):
  arr = list(map(int, input().split()))
  c.append(arr)
  
a = []
for i in range(h):
  arr = list(map(int, input().split()))
  a.append(arr)
  
for i in range(10):
  arr = c[i]
  kakutei = [False] * 10
  kakutei[i] = True
  
  index = -1
  kakutei_num = 1
  while kakutei_num != 10:
    min_num = 11
    for j in range(10):
      if not kakutei[j] and min_num > arr[j]:
        min_num = min(min_num, arr[j])
        index = j
      
    kakutei[index] = True
    kakutei_num += 1
    for j in range(10):
      c[i][j] = min(c[i][j], c[i][index] + c[index][j])
      
ans = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == -1:
      continue
    
    n = a[i][j]
    ans += c[n][1]
    
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    height, width = map(int, input().split())
    change_cost = [list(map(int, input().split())) for _ in range(10)]
    grid = [list(map(int, input().split())) for _ in range(height)]
    for i in range(10):
        for j in range(10):
            for k in range(10):
                change_cost[i][j] = min(change_cost[i][j], change_cost[i][k] + change_cost[k][j])
    answer = 0
    for g in grid:
        for n in g:
            if n != -1:
                answer += change_cost[n][1]
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    height, width = map(int, input().split())
    change_cost = [list(map(int, input().split())) for _ in range(10)]
    grid = [list(map(int, input().split())) for _ in range(height)]
    for i in range(10):
        for j in range(10):
            for k in range(10):
                change_cost[i][j] = min(change_cost[i][j], change_cost[i][k] + change_cost[k][j])
    answer = 0
    for g in grid:
        for n in g:
            if n >= 0:
                answer += change_cost[n][1]
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()

from scipy.sparse.csgraph import floyd_warshall
h,w=map(int,input().split())
table=[]
for i in range(10):
  table.append([int(i) for i in input().split()])
d=floyd_warshall(csgraph=table, directed=False, return_predecessors=False)

ans=0
for i in range(h):
  A=[int(i) for i in input().split()]
  for a in A:
    if a==-1:
      continue
    else:
      ans+=d[a][1]
print(int(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
inf = float("inf")
H, W = map(int, input().split())
graph = np.array([list(map(int, input().split())) for _ in range(10)])

graph = csr_matrix(graph)
shortest_paths = shortest_path(graph, directed=False, method="D")
ans = 0

Alist = [list(map(int, input().split())) for _ in range(H)]
for line in Alist:
    for a in line:
        if a >= 0:
            ans += shortest_paths[a][1]
print(int(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
inf = float("inf")
H, W = map(int, input().split())
graph = np.array([list(map(int, input().split())) for _ in range(10)])

graph = csr_matrix(graph)
shortest_paths = shortest_path(graph, directed=False, method="D")
ans = 0

Alist = [list(map(int, input().split())) for _ in range(H)]
for line in Alist:
    for a in line:
        if a == -1:
            continue
        else:
            ans += shortest_paths[a][1]
print(int(ans))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
c = [0]*10
for i in range(10):
  c[i] = [int(x) for x in 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]])

ans = 0
for i in range(h):
  a = [int(x) for x in input().split()]
  for j in range(w):
    if a[j] == -1:
      continue
    else:
      ans += c[a[j]][1]

print(ans)

Submission status: Wrong Answer

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

INF = 10*10

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

# mp[i][j]..i回でj→1にする時の最小魔力
mp = [[INF]*10 for _ in range(11)]
mp[0][1] = 0
mp[1] = C[:][1]

for i in range(2,11):
    for j in range(10):
        mp[i][j] = min((C[j][k] + mp[i-1][k]) for k in range(10))

cnt = [0]*10
for a in A:
    for i in range(10):
        cnt[i] += a.count(i)

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

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(10)]
cnt = [0]*11
for _ in range(H):
  for a in map(int, input().split()):
    cnt[a] += 1
D = [[C[i][j] for j in range(10)] for i in range(10)]
k = 0
while k < 10:
  i = 0
  while i < 10:
    j = 0
    while j < 10:
      D[i][j] = min(D[i][j], D[i][k]+D[k][j])
      j += 1
    i += 1
  k += 1
print(sum([ cnt[i]*D[i][1] for i in range(1, 10)]))

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

INF=10**4

ans=0

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

Submission status: Wrong Answer

Solution code:
import copy

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

num_dict = {}
for i in range(-1,10):
    new = {i:0}
    num_dict.update(new)

for i in range(h):
    A = list(map(int, input().split()))
    for a in A:
        num_dict[a] += 1

DP = copy.deepcopy(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
for m in range(2, 10):
    ans += DP[m][1] * num_dict[m]

print(ans)

Submission status: Wrong Answer

Solution code:
# むり

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


inf = 10**9+7

point = [inf] * 10


for i in range(10):
    tmp = 0
    for j in range(10):
        tmp += C[i][j]
        point[i] = min(point[i],tmp+C[j][1])
        
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] != -1:
            ans += point[A[i][j]]
            
print(ans)

Submission status: Wrong Answer

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

for i in range(10):
  for j in range(10):
    if i==j:
      continue
    for k in range(10):
      if grid[i][k]+grid[k][j]<grid[i][j]:
        grid[i][j]=grid[i][k]+grid[k][j]
        
ans=0
for i in range(H):
  A=list(map(int,input().split()))
  for a in A:
    if a==-1:
      continue
    ans+=grid[a][1]

print(ans)

Submission status: Wrong Answer

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

for i in range(10):
  for j in range(10):
    for k in range(10):
      if grid[i][k]+grid[k][j]<grid[i][j]:
        grid[i][j]=grid[i][k]+grid[k][j]
        
ans=0
for i in range(H):
  A=list(map(int,input().split()))
  for a in A:
    if a==-1 or a==1:
      continue
    ans+=grid[a][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):
            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(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:
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 != 1 and i != j for i in range(10)] for j in range(10)]
  min_distance_n_to_1 = [INF]*10
  min_distance_n_to_1[1] = 0
  
  # 1から逆にたどっていく
  stack = [1]
  while stack:
    dom = stack.pop()
    # print(dom, min_distance_n_to_1)
    for i in range(10):
      if not search_table[dom][i]: continue
      search_table[dom][i] = False
      stack.append(i)
      if min_distance_n_to_1[i] > min_distance_n_to_1[dom] + graph[i][dom]:
        min_distance_n_to_1[i] = min_distance_n_to_1[dom] + graph[i][dom]
      
      

  # 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:
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 = [INF]*10
  min_distance_n_to_1[1] = 0
  
  # 1から逆にたどっていく
  stack = [1]
  while stack:
    dom = stack.pop()
    for i in range(10):
      if not search_table[dom][i]: continue
      search_table[dom][i] = False
      if min_distance_n_to_1[i] > min_distance_n_to_1[dom] + graph[i][dom]:
        min_distance_n_to_1[i] = min_distance_n_to_1[dom] + graph[i][dom]
        stack.append(i)

  # 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:
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 = [INF]*10
  min_distance_n_to_1[1] = 0
  
  # 1から逆にたどっていく
  stack = [1]
  while stack:
    dom = stack.pop()
    for i in range(10):
      if not search_table[dom][i]: continue
      search_table[dom][i] = False
      stack.append(i)
      if min_distance_n_to_1[i] > min_distance_n_to_1[dom] + graph[i][dom]:
        min_distance_n_to_1[i] = min_distance_n_to_1[dom] + graph[i][dom]

  # 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 = [[-1 for i in range(10)]for j in range(10)]
a = [[-1 for i in range(W)]for j in range(H)]

for i in range(10):
  x = input().split()
  c[i] = [int(i) for i in x]
for i in range(H):
  y = input().split()
  a[i] = [int(i) for i in y]

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

for i in range(H):
  for j in range(2,10):
    ans += a[i].count(j)*c[j][1]
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
c = [[-1 for i in range(10)]for j in range(10)]
a = [[-1 for i in range(W)]for j in range(H)]

for i in range(10):
  x = input().split()
  c[i] = [int(i) for i in x]
for i in range(H):
  y = input().split()
  a[i] = [int(i) for i in y]

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

for i in range(H):
  for j in range(10):
    ans += a[i].count(j)*c[j][1]
print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
field=[[int(i) for i in input().split()] for i in range(10)]
wall=[[int(i) for i in input().split()] for i in range(h)]

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

Submission status: Wrong Answer

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

cost = 0
for a in A:
    for i in a:
        if i > 1:
            cost += dp[i][1]
print(cost)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

H, W = map(int, readline().split())
c = [list(map(int, readline().split())) for i in range(10)]
A = list(map(int, read().split()))


def warshall_floyd(dist):
    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])
    return dist


cc = warshall_floyd(c)

ans = 0
for a in A:
    if a == -1:
        continue
    ans += cc[a][1]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

H, W = map(int, readline().split())
c = [list(map(int, readline().split())) for i in range(10)]
A = list(map(int, read().split()))


def warshall_floyd(dist):
    for i, _ in enumerate(dist):
        for j, _ in enumerate(dist):
            for k, _ in enumerate(dist):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist


cc = warshall_floyd(c)

ans = 0
for a in A:
    if a == -1:
        continue
    ans += cc[a][1]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

H, W = map(int, readline().split())
c = [list(map(int, readline().split())) for i in range(10)]
A = list(map(int, read().split()))


def warshall_floyd(dist):
    for i, _ in enumerate(dist):
        for j, _ in enumerate(dist):
            for k, _ in enumerate(dist):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist


cc = warshall_floyd(c)

ans = 0
for a in A:
    if a == -1:
        continue
    ans += cc[a][1]
print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall

H, W = map(int, input().split())

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
c = []
dicta = {}
dicta[-1] = 0
for i in range(10):
    c.append(list(map(int,input().split())))
    dicta[i] = 0
c = [i for i in zip(*c)]
for i in range(H):
    a = list(map(int,input().split()))
    for i in a:
        dicta[i] += 1
dicta.pop(-1)
cost = [0 for i in range(10)]
def dijkstra_heap(start,node,cost):
    import heapq
    d = [float('inf') for i in range(node)]
    used = [False for i in range(node)]
    d[start] = 0
    d2 = [[0,start]]
    heapq.heapify(d2)
    while True:
        flag = True
        while d2:
            c,v = heapq.heappop(d2)
            flag = False
        if flag:
            break
        used[v] = True
        for j in range(node):
            d[j] = min(d[j],d[v]+cost[v][j])
            if not used[j]:
                heapq.heappush(d2,[d[j],j])
    return d

cost = dijkstra_heap(1,10,c)
ans = 0
for k,v in dicta.items():
    ans += v*cost[k]
print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(10)]
li = [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):
            if lis[i][j] > lis[i][k] + lis[k][j]:
                lis[i][j] = lis[i][k] + lis[k][j]
ans = 0
for i in range(h):
    for num in li[i]:
        if num != -1:
            ans += lis[num][1]
print(ans)