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 main():
    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])
    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)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# 078-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
h,w=IL()
c=[IL() for i in range(10)]
a=[IL() for i 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])
    
ans=0
for i in range(h):
    for j in range(w):
        if a[i][j]==-1:
            continue
        ans+=c[a[i][j]][1]

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
ij = [list(map(int,input().split())) for x in range(10)]
dp = [[100 for i in range(10)] for i in range(10)]
for i in range(10):
    dp[i][0] = ij[i][1]
for i in range(1,10):
    for j in range(10):
        num = dp[j][i-1]
        for k in range(10):
            num = min(num,ij[j][k] + dp[k][j-1])
        dp[j][i] = num
ans = 0
for i in range(h):
    for j in list(map(int,input().split())):
        if j == -1:break
        ans += dp[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)]

for x in range(10):
    for y in range(10):
        for z in range(10):
            c[y][z] = min(c[y][z], c[y][x] + c[x][z])

ans = 0
for x in range(h):
    for y in range(w):
        if a[x][y] > 1:
            ans += c[a[x][y]][1]

print(ans)

Submission status: Wrong Answer

Solution code:
def warshall_floyd(graph):
    num_v = len(graph)
    for i in range(num_v):
        for j in range(num_v):
            for k in range(num_v):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    return graph


h, w = map(int, input().split())
route = []

for i in range(10):
    S = list(map(int, input().split()))
    route.append(S)
graph = warshall_floyd(route)
result = 0
for i in range(h):
    A = list(map(int, input().split()))
    for a in A:
        if a != -1:
            result += graph[a][1]
print(result)

Submission status: Wrong Answer

Solution code:
def warshall_floyd(graph):
    num_v = len(graph)
    for i in range(num_v):
        for j in range(num_v):
            for k in range(num_v):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    return graph


h, w = map(int, input().split())
route = [[float("inf") for _ in range(10)] for _ in range(10)]

for i in range(10):
    S = list(map(int, input().split()))
    for j in range(10):
        route[i][j] = S[j]
graph = warshall_floyd(route)
result = 0
for i in range(h):
    A = list(map(int, input().split()))
    for a in A:
        if a == -1:
            continue
        else:
            result += graph[a][1]
print(result)

Submission status: Wrong Answer

Solution code:
def warshall_floyd(graph):
    num_v = len(graph)
    for i in range(num_v):
        for j in range(num_v):
            for k in range(num_v):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    return graph


h, w = map(int, input().split())
route = [[float("inf") for _ in range(10)] for _ in range(10)]

for i in range(10):
    S = list(map(int, input().split()))
    for j in range(10):
        route[i][j] = S[j]
check_list = []
for i in range(h):
    A = list(map(int, input().split()))
    for a in A:
        if a == -1:
            continue
        else:
            check_list.append(a)
graph = warshall_floyd(route)
result = 0
for c in check_list:
    result += graph[c][1]
print(result)

Submission status: Wrong Answer

Solution code:
def warshall_floyd(graph):
    num_v = len(graph)
    for i in range(num_v):
        for j in range(num_v):
            for k in range(num_v):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    return graph


h, w = map(int, input().split())
route = [[float("inf") for _ in range(10)] for _ in range(10)]

for i in range(10):
    S = list(map(int, input().split()))
    for j in range(10):
        route[i][j] = S[j]
check_list = []
for i in range(h):
    A = list(map(int, input().split()))
    for a in A:
        if a == -1 or a == 1:
            continue
        else:
            check_list.append(a)
graph = warshall_floyd(route)
result = 0
for c in check_list:
    result += graph[c][1]
print(result)

Submission status: Wrong Answer

Solution code:
from heapq import *
from collections import Counter
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 = [0]*10
for i in range(H):
    CA = Counter(A[i])
    for j in range(10):
        N[j] += CA[j]
L = [(0,1)]
V = [-1]*10
while L:
    d, v = heappop(L)
    if not V[v] == -1:
        continue
    else:
        V[v] = d
    for i in range(1,10):
        if V[i] == -1:
            heappush(L, (d+C[i][v], i))
ans = 0
for i in range(10):
    ans += V[i]*N[i]
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import *
from collections import Counter
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 = [0]*10
for i in range(H):
    CA = Counter(A[i])
    for j in range(2,10):
        N[j] += CA[j]
L = [(0,1)]
V = [0] + [-1]*9
while L:
    d, v = heappop(L)
    if not V[v] == -1:
        continue
    else:
        V[v] = d
    for i in range(1,10):
        if V[i] == -1:
            heappush(L, (d+C[i][v], i))
ans = 0
for i in range(2,10):
    ans += V[i]*N[i]
print(ans)

Submission status: Wrong Answer

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

def w_f():
    cost=[]
    for i in range(10):
        cost.append(list(map(int,input().strip().split(' '))))

    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
    
d=w_f()
ans=0
for i in range(H):
    a=list(map(int,input().strip().split(' ')))
    for j in a:
        if j!=-1:
            ans+=d[j][1]
print(ans)

Submission status: Wrong Answer

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

V=10
E=45
inf=10**9

def w_f():
    cost=[]
    for i in range(10):
        cost.append(list(map(int,input().strip().split(' '))))

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


d=w_f()

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

print(ans)

Submission status: Wrong Answer

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

V=10
E=45
inf=10**9

def w_f():
    cost=[[None]*10 for i in range(10)]
    for i in range(10):
        c=list(map(int,input().strip().split(' ')))
        for j in range(10):
            cost[i][j]=c[j]

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


d=w_f()

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

print(ans)

Submission status: Wrong Answer

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

V=10
E=45
inf=10**9

def w_f():
    inf=10**9
    cost=[[inf]*V for i in range(V)]
    edge=[]
    for i in range(10):
        c=list(map(int,input().strip().split(' ')))
        for j in range(10):
            cost[i][j]=c[j]
            edge.append([i,j])

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

    
    
    
d=w_f()

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

print(ans)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
c=[[int(i) for i in input().split()] for i in range(10)]
Points=[]
for i in range(0,10):
  if i==1:
    Points.append(0)
  else:
    Roots=[[i]]
    Roots_finished=[]
    for R in Roots:
      for j in range(10):
        if R[-1]==1:
          Roots_finished.append(R)
          break
        elif j in R:
          pass
        elif j==1:
          R_kari=list(R)
          R_kari.append(1)
          Roots.append(R_kari)
        elif c[R[-1]][j]<c[R[-1]][1]:
          R_kari=list(R)          
          R_kari.append(j)
          Roots.append(R_kari)
    S=1000000000000
    for r in Roots_finished:
      S_kari=0
      j=r[0]
      for i in r:
        S_kari+=c[j][i]
        j=i
      if S>S_kari:
        S=S_kari
    Points.append(S)
Magic_Power=0
for i in range(H):
  for j in input().split():
    if int(j)==-1:
      j=1
    Magic_Power+=Points[int(j)]
print(Magic_Power)   
print(Points)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
c=[[int(i) for i in input().split()] for i in range(10)]
Points=[]
for i in range(0,10):
  if i==1:
    Points.append(0)
  else:
    Roots=[[i]]
    Roots_finished=[]
    for R in Roots:
      for j in range(10):
        if j in R:
          pass
        elif R[-1]==1:
          Roots_finished.append(R)
          break
        elif j==1:
          R_kari=list(R)
          R_kari.append(1)
          Roots.append(R_kari)
        elif c[R[-1]][j]<c[R[-1]][1]:
          R_kari=list(R)          
          R_kari.append(j)
          Roots.append(R_kari)
    S=1000000000000
    for r in Roots_finished:
      S_kari=0
      j=r[0]
      for i in r:
        S_kari+=c[j][i]
        j=i
      if S>S_kari:
        S=S_kari
    Points.append(S)
Magic_Power=0
for i in range(H):
  for j in input().split():
    if int(j)==-1:
      j=1
    Magic_Power+=Points[int(j)]
print(Magic_Power)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
c=[[int(i) for i in input().split()] for i in range(10)]
Points=[]
n=2
for i in range(0,10):
  if i==1:
    Points.append(0)
  else:
    Roots=[[i]]
    Roots_finished=[]
    for R in Roots:
      for j in range(10):
        if j in R:
          pass
        elif R[-1]==1:
          Roots_finished.append(R)
          break
        elif len(R)>11:
          break
        elif j==1:
          R_kari=list(R)
          R_kari.append(1)
          Roots.append(R_kari)
        elif c[R[-1]][j]<c[R[-1]][1]:
          R_kari=list(R)          
          R_kari.append(j)
          Roots.append(R_kari)
    S=1000000000000
    for r in Roots_finished:
      S_kari=0
      j=r[0]
      for i in r:
        S_kari+=c[j][i]
        j=i
      if S>S_kari:
        S=S_kari
    Points.append(S)
Magic_Power=0
for i in range(H):
  for j in input().split():
    if int(j)==-1:
      j=1
    Magic_Power+=Points[int(j)]
print(Magic_Power)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
c=[[int(i) for i in input().split()] for i in range(10)]
Points=[]
n=2
for i in range(0,10):
  if i==1:
    Points.append(0)
  else:
    Point_Candidate=c[i][1]
    Roots=[[i]]
    Roots_finished=[]
    for R in Roots:
      for j in range(10):
        if j in R:
          pass
        elif R[-1]==1:
          Roots_finished.append(R)
          break
        elif len(R)>11:
          break
        elif j==1:
          R_kari=list(R)
          R_kari.append(1)
          Roots.append(R_kari)
        elif c[R[-1]][j]<c[R[-1]][1]:
          R_kari=list(R)          
          R_kari.append(j)
          Roots.append(R_kari)
    S=100000
    for r in Roots_finished:
      S_kari=0
      j=r[0]
      for i in r:
        S_kari+=c[j][i]
        j=i
      if S>S_kari:
        S=S_kari
    Points.append(S)
Magic_Power=0
for i in range(H):
  for j in input().split():
    if int(j)==-1:
      j=1
    Magic_Power+=Points[int(j)]
print(Magic_Power)

Submission status: Wrong Answer

Solution code:
def search_min_cost(nums, prev_num, min_cost, cost, c):
    _last_min_cost = min_cost
    if len(nums) != 0:
        _min_cost = cost + c[prev_num][1]
        if min_cost < _min_cost:
            _min_cost = min_cost
        for i in nums:
            _nums = nums[:]
            _nums.remove(i)
            next_cost = cost + c[prev_num][i]
            if _min_cost <= next_cost:
                if _min_cost < _last_min_cost:
                    _last_min_cost = _min_cost
            else:
                m = search_min_cost(
                    _nums, i, _min_cost, next_cost, c)
                if m < _last_min_cost:
                    _last_min_cost = m
    return _last_min_cost


H, W = map(int, input().split())
# c[y][x]: y行目、x文字目
c = [list(map(int, input().split())) for _ in range(10)]
# A[y][x]: y行目、x文字目
A = [list(map(int, input().split())) for _ in range(H)]
min_cost_map = {}
min_cost_map[1] = 0

nums = [0, 2, 3, 4, 5, 6, 7, 8, 9]
for i in nums:
    _nums = nums[:]
    _nums.remove(i)
    min_cost_map[i] = search_min_cost(_nums, i, 1001, 0, c)
# print(min_cost_map)
cost = 0
for i in range(H):
    for j in range(W):
        n = A[i][j]
        if n != -1:
            cost += min_cost_map[n]
print(cost)

Submission status: Wrong Answer

Solution code:
from scipy.sparse import csgraph
#root = csgraph.floyd_warshall(root)

def ABC079D():
    H, W = map(int, input().split())
    c = [list(map(int, input().split())) for i in range(10)]
    A = [list(map(int, input().split())) for i in range(H)]
    c = csgraph.floyd_warshall(c, False)
    #print(c)
    ans = 0
    for i in A:
        for j in i:
            if j != -1:
                ans += c[j][1]
                #print(c[j][1], j)
    print(int(ans))
ABC079D()

Submission status: Wrong Answer

Solution code:
from scipy.sparse import csgraph
#root = csgraph.floyd_warshall(root)

def ABC079D():
    H, W = map(int, input().split())
    c = [list(map(int, input().split())) for i in range(10)]
    A = [list(map(int, input().split())) for i in range(H)]
    c = csgraph.floyd_warshall(c, False)
    #print(c)
    ans = 0
    for i in A:
        for j in i:
            if j != -1:
                ans += c[j][1]
                #print(c[j][1], j)
    print(ans)
ABC079D()

Submission status: Wrong Answer

Solution code:
from scipy.sparse import csgraph
#root = csgraph.floyd_warshall(root)

def ABC079D():
    H, W = map(int, input().split())
    c = [list(map(int, input().split())) for i in range(10)]
    A = [list(map(int, input().split())) for i in range(H)]
    c = csgraph.floyd_warshall(c, False)
    print(c)
    ans = 0
    for i in A:
        for j in i:
            if j != -1:
                ans += c[j][1]
                #print(c[j][1], j)
    print(ans)
ABC079D()

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
C = []
A = []
for i in range(10) :
    C.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) :
            C[i][j] = min(C[i][j], C[i][k]+C[k][j])
ans = 0
for row in A :
    for a in row :
        if a == -1 or a == 1 :
            continue
        else :
            ans += C[a][1]
print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
grid = []
for i in range(10):
    array = list(map(int, input().strip().split(' ')))
    grid.append(array)
wall = []
for i in range(h):
    array = list(map(int, input().strip().split(' ')))
    wall.append(array)
def warshall_floyd(n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j])
warshall_floyd(10)
cost=[]
for arrays in grid:
  cost.append(arrays[1])
ans = 0
for arrays in wall:
  for nums in arrays:
    ans += cost[nums]
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
h,w = map(int, input().split())

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

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

ret = 0
for _ in range(h):
    for a in map(int, input().split()):
        if a>1:
            ret += c[a][1]

print(ret)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
h,w = map(int, input().split())

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

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

ret = 0
for _ in range(h):
    for a in map(int, input().split()):
        if a>1:
            ret += c[a][1]

print(ret)

Submission status: Wrong Answer

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

wall = [list(map(int, input().split())) for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if wall[i][j] > 0:
            num = wall[i][j]
            ans += d[num][1]

print(ans)

Submission status: Wrong Answer

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

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

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

print(ans)

Submission status: Wrong Answer

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

for p in range(10):
    for q in range(10):
        for r in range(10):
            c[q][r] = min(c[q][r], c[q][p]+c[p][r])

ans = 0
for k in range(H):
    for l in range(W):
        if A[k][l] > 0:
            ans += c[A[k][l]][1]
print(ans)

Submission status: Wrong Answer

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


cost = 0

for i in range(H):
    A = list(map(int, input().split()))
    for j in range(len(A)):
        if A[j] != -1 and A[j] != 1:
            cost += D[A[j]][1]

print(cost)

Submission status: Wrong Answer

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

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

for a in range(10):
    for b in range(10):
        for c in range(10):
            A[a][b]=min(A[a][b],A[a][c]+A[c][b])

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

Submission status: Wrong Answer

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

A=[]
for i in range(10):
    B=list(map(int,input().split()))
    A.append(B)
#print(A)

for a in range(10):
    for b in range(10):
        for c in range(10):
            A[a][b]=min(A[a][b],A[a][c]+A[c][b])

ans=0
D=[]
for j in range(H):
    C=list(map(int,input().split()))
    D.append(C)
        
for k in range(H):
    for l in range(W):
        if D[k][l]!=(-1):
            ans+=A[D[k][l]][1]
print(ans)

Submission status: Wrong Answer

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

A=[]
for i in range(10):
    B=list(map(int,input().split()))
    A.append(B)
#print(A)

for a in range(10):
    for b in range(10):
        for c in range(10):
            A[a][b]=min(A[a][b],A[a][c]+A[c][b])

ans=0
for x in range(H):
    C=list(map(int,input().split()))
    for y in range(W):
        
        if C[y]!=(-1):
            ans+=A[C[y]][1]
print(ans)

Submission status: Wrong Answer

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

for a in range(10):
    for b in range(10):
        for c in range(10):
            list1[a][b]=min(list1[a][b],list1[a][c]+list1[c][b])
#print(list1)

ans=0
for x in range(H):
    list4=list(map(int,input().split()))
    for y in range(W):
        if list4[y]==(-1):
            pass
        else:
            ans+=list1[list4[y]][1]
print(ans)

Submission status: Wrong Answer

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

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

v=[[l[j][1] if j>=0 else 0 for j in i] for i in o]
print(sum(map(sum,v)))

Submission status: Wrong Answer

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

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

v=[[l[j][1] if j!=-1 else 0 for j in i] for i in o]
print(sum(map(sum,v)))

Submission status: Wrong Answer

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

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

v=[[l[j][1] if j!=-1 else 0 for j in i] for i in o]
print(sum([sum(i) for i in v]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
h,w = map(int,raw_input().split())
d = [map(int,raw_input().split()) 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], d[i][k] + d[k][j])
arr = [map(int,raw_input().split()) for i in range(h)]

print sum(sum(d[a][1] if a>=0 else 0 for a in aa) for aa in arr)

Submission status: Wrong Answer

Solution code:
h,w = map(int,raw_input().split())
d = [map(int,raw_input().split()) 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], d[i][k] + d[k][j])

ans = 0
for i in range(h):
	for j in map(int,raw_input().split()):
		if j != -1 :
			ans += d[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):
            if c[i][k] > c[i][j] + c[j][k]:
                c[i][k] = c[i][j] + c[j][k]
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == -1 or A[i][j] == 1:
            continue
        else:
            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 x 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])

ans = 0

for i in range(h):
    for j in range(w):
        if a[i][j] != 0 and a[i][j] != -1:
            ans += c[a[i][j]][1]

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import product

H, W = map(int, input().split())
c = [[int(x) for x in input().split()] for _ in range(10)]
A = defaultdict(int)
for _ in range(H):
    for x in input().split():
        x = int(x)
        if x != -1 and x != 1:
            A[x] += 1

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

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

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
C=[]
A=[]
for i in range(10):
    C.append(list(map(int,input().split())))
for i in range(H):
    A.append(list(map(int,input().split())))
# WF
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(sum(sum(C[i][1] for i in AA if i >= 0) for AA in A))
ans=0
for AA in A:
    for a in AA:
        if a==-1:continue
        ans+=C[a][1]
print(ans)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
C=[]
A=[]
for i in range(10):
    C.append(list(map(int,input().split())))
for i in range(H):
    A.append(list(map(int,input().split())))
# WF
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(sum(sum(C[i][1] for i in AA if i >= 0) for AA in A))

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
C=[]
A=[]
from queue import Queue
def djcstra(frm,to,D):
    dist=D[frm]
    Q=sorted(range(len(D)) , key=lambda x:-dist[x])
    Q.pop(-1)
    while len(Q):
        u=Q.pop(-1)
        if u==to:break
        for i,d in enumerate(D[u]):
            if dist[i] >dist[u]+d:
                dist[i]=dist[u]+d
        Q=sorted(sorted(Q , key=lambda x:-dist[x]))
    return dist[to]
for i in range(10):
    C.append(list(map(int,input().split())))
for i in range(H):
    A.append(list(map(int,input().split())))
cst=[float('inf')]*10
for i in range(10):
    cst[i]=djcstra(i,1,C)
print(sum(sum(cst[i] for i in AA if i >= 0) for AA in A))

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
C=[]
A=[]
from queue import Queue
def djcstra(frm,to,D):
    dist=D[frm]
    Q=sorted(range(len(D)) , key=lambda x:-dist[x])
    Q.pop(-1)
    while len(Q):
        u=Q.pop(-1)
        if u==to:break
        for i,d in enumerate(D[u]):
            if dist[i] >dist[u]+d:
                dist[i]=dist[u]+d
        Q=sorted(sorted(Q , key=lambda x:-dist[x]))
    return dist[to]
for i in range(10):
    C.append(list(map(int,input().split())))
for i in range(H):
    A.append(list(map(int,input().split())))
cst=[float('inf')]*10
for i in range(10):
    cst[i]=djcstra(i,1,C)
sum(sum(cst[i] for i in AA if i >= 0) for AA in A)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
costs = [list(map(int, input().split())) for _ in range(10)]
wall = [list(map(int, input().split())) for _ in range(H)]
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])

d = {-1: 0, 0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
for i in wall:
    for n in range(0, 10):
        d[n] += i.count(n)
min_cost = 0
for i in range(2, 10):
    min_cost += d[i] * costs[i][1]
print(min_cost)

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 rA in A:
    for n in rA:
        if n >= 0:
            ans += c[n][1]

print(ans)