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())
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 j in range(w):
        if li[i][j] != -1:
            ans += lis[li[i][j]][1]
print(ans)

Submission status: Wrong Answer

Solution code:
# AGC079 D - Wall
h,w=map(int,input().split())
c=[list(map(int,input().split())) for i in range(10)]
a=[list(map(int,input().split())) for i in range(h)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            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:
            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 k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][k] = min(c[i][j], c[i][k]+c[k][j])

ans = 0
for row in A:
    for a in row:
        if a < 0:
            continue
        ans += c[a][1]
print(ans)

Submission status: Wrong Answer

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

WF = []
wall = []
count = 0

for _ in range(10):
    array = list(map(int, input().split()))
    WF.append(array)

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

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

distance_to_one = []
for i in range(10):
    distance_to_one.append(WF[i][1])

for i in range(h):
    for j in range(w):
        num = wall[i][j]
        if num <= 1:
            num = 1
        count += distance_to_one[num]

print(count)

Submission status: Wrong Answer

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

route_list = []
wall = []
count = 0

for _ in range(10):
    array = list(map(int, input().split()))
    route_list.append(array)

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

node_num = len(route_list) #ノードの数

route = []

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

distance_to_one = []
for i in range(10):
    distance_to_one.append(route_list[i][1])

for i in range(h):
    for j in range(w):
        num = wall[i][j]
        if num <= 1:
            num = 1
        count += distance_to_one[num]

print(count)

Submission status: Wrong Answer

Solution code:
import itertools
import collections


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

route_list = []
wall = []
count = 0

for _ in range(10):
    array = list(map(int, input().split()))
    route_list.append(array)

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

node_num = len(route_list) #ノードの数

route = []

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

distance_to_one = []
for i in range(10):
    distance_to_one.append(route_list[i][1])

flattened_wall = list(itertools.chain.from_iterable(wall))

c = collections.Counter(flattened_wall)
for i, j in c.items():
    if i == -1 or i == 1 or i == 0:
        continue
    else:
        count += distance_to_one[i] * j

print(count)

Submission status: Wrong Answer

Solution code:
import itertools
import collections


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

route_list = []
wall = []
count = 0

for _ in range(10):
    array = list(map(int, input().split()))
    route_list.append(array)

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

node_num = len(route_list) #ノードの数

route = []

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

distance_to_one = []
for i in range(10):
    distance_to_one.append(route_list[i][1])

flattened_wall = list(itertools.chain.from_iterable(wall))

c = collections.Counter(flattened_wall)
for i, j in c.items():
    if i == -1 and i == 1 and i == 0:
        continue
    else:
        count += distance_to_one[i] * j

print(count)

Submission status: Wrong Answer

Solution code:
import itertools
import collections


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

route_list = []
wall = []
count = 0

for _ in range(10):
    array = list(map(int, input().split()))
    route_list.append(array)

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

node_num = len(route_list) #ノードの数
# d = [[10000000000 for _ in range(10)] for _ in range(10)]

route = []

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

distance_to_one = []
for i in range(10):
    distance_to_one.append(route_list[i][1])

flattened_wall = list(itertools.chain.from_iterable(wall))

c = collections.Counter(flattened_wall)
for i, j in c.items():
    if i == -1:
        continue
    elif i == 1:
        collections
    else:
        count += distance_to_one[i] * j

print(count)

Submission status: Wrong Answer

Solution code:
import math
import itertools
import collections


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

route_list = []
wall = []
count = 0

for _ in range(10):
    array = list(map(int, input().split()))
    route_list.append(array)

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

node_num = len(route_list) #ノードの数

route = []

for i in range(10):
    now = i
    unsearched_nodes = list(range(node_num)) # 未探索ノード
    distance = [100000000000000000] * node_num # ノードごとの距離のリスト
    distance[now] = 0 # 初期のノードの距離は0とする

    while len(unsearched_nodes) > 0:
        for node in range(node_num):
            if now == node:
                continue
            else:
                distance[node] = min(distance[now] + route_list[now][node], distance[node])
        unsearched_nodes.remove(now)
        if len(unsearched_nodes) > 0:
            now = unsearched_nodes[0]
    route.append(distance)

distance_to_one = []
for i in range(10):
    distance_to_one.append(route[i][1])

flattened_wall = list(itertools.chain.from_iterable(wall))

c = collections.Counter(flattened_wall)
for i, j in c.items():
    if i == -1:
        continue
    elif i == 1:
        collections
    else:
        count += distance_to_one[i] * j

print(count)

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

#各数字を1に変えるための最小の魔力を求める
#ワーシャルフロイド法
dp=[[1000*10 for _ in range(10)] for __ in range(10)]
for i in range(10):
    for j in range(10):
        dp[i][j]=C[i][j]
for i in range(10): #直前の数字
    for j in range(10): #最初の数字
        for k in range(10): #変化後の数字
            dp[j][k]=min(dp[j][k],dp[j][i]+C[i][k])
min_mp=[0]*10
for i in range(10):
    min_mp[i]=dp[i][1]

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

#各数字を1に変えるための最小の魔力を求める
#dp[最初の数字][変化後の数字]=最小魔力
dp=[[1000*10 for _ in range(10)] for __ in range(10)]
for i in range(10):
    for j in range(10):
        dp[i][j]=C[i][j]
for i in range(10): #最初の数字
    for j in range(10): #直前の数字
        for k in range(10): #変化後の数字
            dp[i][k]=min(dp[i][k],dp[i][j]+C[j][k])
min_mp=[0]*10
for i in range(10):
    min_mp[i]=dp[i][1]

ans=0
for i in range(H):
    for j in range(W):
        a = A[i][j]
        if a!=-1:
            ans+=min_mp[a]
print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc079/tasks/abc079_d

from collections import Counter
from functools import reduce

def warshall(matrix, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if matrix[i][j] + matrix[j][k] < matrix[i][k]:
                    matrix[i][k] = matrix[i][j] + matrix[j][k]

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

counter = {i:0 for i in range(10)}
for _ in range(h):
    for a in map(int, input().split()):
        if a > -1:
            counter[a] += 1
    # counter.update(Counter(map(int, input().split())))
warshall(magic, 10)

ans = 0
for k,v in counter.items():
    ans += magic[k][1] * v
print(ans)
# print(reduce(lambda x,y:x+y, [magic[k][1] * v for k,v in counter.items() if k > -1]))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc079/tasks/abc079_d

from collections import Counter
from functools import reduce

def warshall(matrix, n):
    for i in range(n):
        for k in range(n):
            for j in range(n):
                if matrix[i][j] + matrix[j][k] < matrix[i][k]:
                    matrix[i][k] = matrix[i][j] + matrix[j][k]

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

counter = {i:0 for i in range(10)}
for _ in range(h):
    for a in map(int, input().split()):
        if a > -1:
            counter[a] += 1
    # counter.update(Counter(map(int, input().split())))
warshall(magic, 10)

ans = 0
for k,v in counter.items():
    ans += magic[k][1] * v
print(ans)
# print(reduce(lambda x,y:x+y, [magic[k][1] * v for k,v in counter.items() if k > -1]))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc079/tasks/abc079_d

from collections import Counter
from functools import reduce

def warshall(matrix, n):
    for i in range(n):
        for k in range(n):
            for j in range(n):
                if matrix[i][j] + matrix[j][k] < matrix[i][k]:
                    matrix[i][k] = matrix[i][j] + matrix[j][k]

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

counter = {i:0 for i in range(10)}
for _ in range(h):
    for a in map(int, input().split()):
        if a > -1:
            counter[a] += 1
    # counter.update(Counter(map(int, input().split())))
warshall(magic, 10)

print(reduce(lambda x,y:x+y, [magic[k][1] * v for k,v in counter.items() if k > -1]))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc079/tasks/abc079_d

from collections import Counter
from functools import reduce

def warshall(matrix, n):
    for i in range(n):
        for k in range(n):
            for j in range(n):
                if matrix[i][j] + matrix[j][k] < matrix[i][k]:
                    matrix[i][k] = matrix[i][j] + matrix[j][k]
    return matrix

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

counter = Counter()
for _ in range(h):
    counter.update(Counter(map(int, input().split())))
magic = warshall(magic, 10)

print(reduce(lambda x,y:x+y, [magic[k][1] * v for k,v in counter.items() if k > -1]))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc079/tasks/abc079_d

from collections import Counter
from functools import reduce

def warshall(matrix, n):
    for i in range(n):
        for k in range(n):
            for j in range(n):
                if matrix[i][j] + matrix[j][k] < matrix[i][k]:
                    matrix[i][k] = matrix[i][j] + matrix[j][k]
    return matrix

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

counter = Counter()
for _ in range(h):
    counter.update(Counter(map(int, input().split())))
power = warshall(magic, 10)

print(reduce(lambda x,y:x+y, [magic[k][1] * v for k,v in counter.items() if k > -1]))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc079/tasks/abc079_d

from collections import Counter
from functools import reduce

def warshall(matrix, n):
    for i in range(n):
        for k in range(n):
            for j in range(n):
                if matrix[i][j] + matrix[j][k] < matrix[i][k]:
                    matrix[i][k] = matrix[i][j] + matrix[j][k]

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

counter = Counter()
for _ in range(h):
    counter.update(Counter(map(int, input().split())))
warshall(magic, 10)

print(reduce(lambda x,y:x+y, [magic[k][1] * v for k,v in counter.items() if k > -1]))
# print(counter)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc079/tasks/abc079_d

from collections import Counter
from functools import reduce

def warshall(matrix, n):
    for i in range(n):
        for k in range(n):
            for j in range(n):
                if matrix[i][j] + matrix[j][k] < matrix[i][k]:
                    matrix[i][k] = matrix[i][j] + matrix[j][k]

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

c = Counter()
for _ in range(h):
    c.update(Counter(map(int, input().split())))
# warshall(power, 10)
from scipy.sparse.csgraph import dijkstra as di
power = di(power)
# ans = 0
# for k,v in c.items():
#     if k > -1:
#         ans += power[k][1] * v
# print(ans)
print(reduce(lambda x,y:x+y, [power[i][1] * c.get(i,0) for i in range(10)]))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc079/tasks/abc079_d

from collections import Counter
from functools import reduce

def warshall(matrix, n):
    for i in range(n):
        for k in range(n):
            for j in range(n):
                if matrix[i][j] + matrix[j][k] < matrix[i][k]:
                    matrix[i][k] = matrix[i][j] + matrix[j][k]

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

c = Counter()
for _ in range(h):
    c.update(Counter(map(int, input().split())))
warshall(power, 10)
ans = 0
for k,v in c.items():
    if k > -1:
        ans += power[k][1] * v
print(ans)
# print(reduce(lambda x,y:x+y, [power[i][1] * c.get(i,0) for i in range(10)]))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc079/tasks/abc079_d

from collections import Counter
from functools import reduce

def warshall(matrix, n):
    for i in range(n):
        for k in range(n):
            for j in range(n):
                if matrix[i][j] + matrix[j][k] < matrix[i][k]:
                    matrix[i][k] = matrix[i][j] + matrix[j][k]

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

c = Counter()
for _ in range(h):
    c.update(Counter(map(int, input().split())))
warshall(power, 10)
print(reduce(lambda x,y:x+y, [power[i][1] * c.get(i, 0) for i in range(10)]))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc079/tasks/abc079_d

from collections import Counter
from functools import reduce

def warshall(matrix, n):
    for i in range(n):
        for k in range(n):
            for j in range(n):
                if matrix[i][j] + matrix[j][k] < matrix[i][k]:
                    matrix[i][k] = matrix[i][j] + matrix[j][k]

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

c = Counter()
for _ in range(h):
    c.update(Counter(map(int, input().split())))
warshall(power, 10)
print(reduce(lambda x,y:x+y, [power[i][1] * c[i] for i in range(10)]))

Submission status: Wrong Answer

Solution code:
def main():
    h,w = map(int,input().split())
    c = []
    for i in range(0,10):
        cc = list(map(int,input().split()))
        c.append(cc)
    a = []
    for i in range(0,h):
        aa = list(map(int,input().split()))
        a.append(aa)
    # ワーシャルフロイド（最短経路だす）
    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])
    cnt = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] != 1 and a[i][j] > 0:
                cnt += c[a[i][j]][1]
    print(cnt)


if __name__=='__main__':
    main()

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

# C[i][j]はiをjにするのに必要なコスト
# warshal-floyd
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 range(10):
    print(C[i])
ans = 0
for i in range(h):
    for j in range(w):
        if A[i][j] == -1:
            ans += 0
        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 i in range(h)]

# C[i][j]はiをjにするのに必要なコスト
# warshal-floyd
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 ans == -1:
            ans += 0
        else:
            ans += C[A[i][j]][1]
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

H,W = map(int,input().split())
C = [list(map(int,input().split())) for _ in range(10)]
cntA = {}
for _ in range(H):
  for a in map(int,input().split()):
    if a not in cntA:
      cntA[a] = 1
    else:
      cntA[a] += 1

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 key, num in cntA.items():
  if key not in [-1,1]:
    ans += C[key][1]*num
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

H,W = map(int,input().split())
C = [list(map(int,input().split())) for _ in range(10)]
cntA = {}
for _ in range(H):
  for a in map(int,input().split()):
    if a not in cntA:
      cntA[a] = 1
    else:
      cntA[a] += 1

dp = copy.deepcopy(C)

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

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]+C[k][j])
      
ans = 0
for key, num in cntA.items():
  if key not in [-1,1]:
    ans += dp[key][1]*num
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

H,W = map(int,input().split())
C = [list(map(int,input().split())) for _ in range(10)]
cntA = {}
for _ in range(H):
  for a in map(int,input().split()):
    if a not in cntA:
      cntA[a] = 1
    else:
      cntA[a] += 1

dp = copy.deepcopy(C)

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]+C[k][j])
      
ans = 0
for key, num in cntA.items():
  if key not in [-1,1]:
    ans += dp[key][1]*num
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

H,W = map(int,input().split())
C = [list(map(int,input().split())) for _ in range(10)]
cntA = {}
for _ in range(H):
  for a in map(int,input().split()):
    if a not in cntA:
      cntA[a] = 1
    else:
      cntA[a] += 1

dp = copy.deepcopy(C)

for j in range(10):
  for i in range(10):
    for k in range(10):
      dp[i][j] = min(dp[i][j], dp[i][k]+C[k][j])
      
ans = 0
for key, num in cntA.items():
  if key not in [-1,1]:
    ans += dp[key][1]*num
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

H,W = map(int,input().split())
C = [list(map(int,input().split())) for _ in range(10)]
cntA = {}
for _ in range(H):
  for a in map(int,input().split()):
    if a not in cntA:
      cntA[a] = 1
    else:
      cntA[a] += 1

dp = copy.deepcopy(C)

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

for i in range(10):
  for j in range(10):
    for k in range(10):
      dp[j][i] = min(dp[j][i], dp[k][i]+C[j][k])
      
ans = 0
for key, num in cntA.items():
  if key not in [-1,1]:
    ans += dp[key][1]*num
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

H,W = map(int,input().split())
C = [list(map(int,input().split())) for _ in range(10)]
cntA = {}
for _ in range(H):
  for a in map(int,input().split()):
    if a not in cntA:
      cntA[a] = 1
    else:
      cntA[a] += 1

dp = copy.deepcopy(C)

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

ans = 0
for key, num in cntA.items():
  if key not in [-1,1]:
    ans += dp[key][1]*num
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	H, W = MAP()
	TABLE = [MAP() for _ in range(10)]
	A = [MAP() for _ in range(H)]

	to_one = [t[1] for t in TABLE]
	mv = float("INF")
	mi = -1
	for i,to in enumerate(to_one):
		if i == 1: continue
		if to <= mv:
			mi = i
			mv = to

	queue = deque()
	queue.append(mi)
	end = True
	while queue:
		# print(queue)
		mi = queue.popleft()
		for i, t in enumerate(TABLE):
			if i == mi: continue
			if t[mi]+to_one[mi] < to_one[i]:
				to_one[i] = t[mi]+to_one[mi]
				end = False
				queue.append(i)
		if end:
			break
	
	# print(to_one)
	
	ans = 0
	for row in A:
		for a in row:
			if a != -1: ans += to_one[a]
	
	print(ans)

if __name__ == '__main__':
	main()

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

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import shortest_path


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

graph = np.zeros((10,10))
for i in range(10):
    for j in range(10):
        graph[i,j] = c[i][j]
dist = shortest_path(graph,directed=True).astype(int)

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
h,w=map(int, input().split(' '))
tbl = [list(map(int, input().split(' '))) for i in range(10)]
tbli = list(zip(*tbl))
cost = [10**18]*10
cost[1]=0
sorttool = [0,1,2,3,4,5,6,7,8,9]
order = list(zip(tbli[1],sorttool))
order.sort()
for i,(c,x) in enumerate(order):
    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().split(' '))) for i in range(10)]
tbli = list(zip(*tbl))
cost = [10**18]*10
cost[1]=0
sorttool = [0,1,2,3,4,5,6,7,8,9]
order = list(zip(tbli[1],sorttool))
order.sort()
del order[0]
for i,(c,x) in enumerate(order):
    cost[x] = min(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().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()
del order[0]
for i,(c,x) in enumerate(order):
    cost[x] = min(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):
    cost[x] = min(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)