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: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    # 最短経路問題で使われるアルゴリズムの１つ。
    # グラフ上の全ての頂点間の最短経路を探す
    # 負の閉路（辺の重みの和が負になるような閉路）がない限り、負の辺があっても使える。

    # 負の閉路を持つ場合は'NEGATIVE CYCLE'を、そうでない場合には(i,j)成分に
    # 頂点iから頂点jへの最短経路の距離を格納するdist_listをprintする関数
    def warshall_floyd(v_num, dist_lst):
        for k in range(v_num):
            for i in range(v_num):
                for j in range(v_num):
                    # i→k→jがつながっててしかもi→jルートよりもイケてるなら更新
                    if dist_lst[i][k] != INF and dist_lst[k][j] != INF:
                        if dist_lst[i][j] > dist_lst[i][k] + dist_lst[k][j]:
                            dist_lst[i][j] = dist_lst[i][k] + dist_lst[k][j]

        return dist_lst

    H, W = map(int, input().split())
    # 頂点の数と辺の数
    v_num, e_num = 10, 100

    # 配列dist_lst[a][b]には頂点a,b間の辺のコストを入れておき、
    # a=bの時は0を、a,b間の辺が存在しないときはINFを入れておく。
    INF = 10 ** 20
    dist_lst = [[INF] * v_num for _ in range(v_num)]

    costs = [[i for i in list(map(int, input().split()))] for _ in range(10)]
    for s in range(10):
        for t in range(10):
            dist_lst[s][t] = costs[s][t]

    dist_lst = warshall_floyd(v_num, dist_lst)
    wall = [[i for i in list(map(int, input().split()))] for _ in range(10)]
    cnt = 0
    for h in range(H):
        for w in range(W):
            val = wall[h][w]
            if val == -1 or val == 1:
                continue
            else:
                cnt += dist_lst[val][1]
    print(cnt)


resolve()

Submission status: Runtime Error

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    H, W = map(int, input().split())

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

    graph = csr_matrix(graph)

    dist_matrix = floyd_warshall(csgraph=graph, directed=True, return_predecessors=False)
    dist_matrix = list(dist_matrix)
    wall = [[i for i in list(map(int, input().split()))] for _ in range(10)]
    cnt = 0
    for h in range(H):
        for w in range(W):
            val = wall[h][w]
            if val != -1 and val != 1:
                cnt += dist_matrix[val][1]
    print(int(cnt))


resolve()

Submission status: Runtime Error

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()


def resolve():
    H, W = map(int, input().split())

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

    graph = csr_matrix(graph)

    dist_matrix = floyd_warshall(csgraph=graph, directed=True, return_predecessors=False)
    dist_matrix = list(dist_matrix)
    wall = [[i for i in list(map(int, input().split()))] for _ in range(10)]
    cnt = 0
    for h in range(H):
        for w in range(W):
            val = wall[h][w]
            if val != -1 and val != 1:
                cnt += dist_matrix[val][1]
    print(int(cnt))


resolve()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    # 最短経路問題で使われるアルゴリズムの１つ。
    # グラフ上の全ての頂点間の最短経路を探す
    # 負の閉路（辺の重みの和が負になるような閉路）がない限り、負の辺があっても使える。

    # 負の閉路を持つ場合は'NEGATIVE CYCLE'を、そうでない場合には(i,j)成分に
    # 頂点iから頂点jへの最短経路の距離を格納するdist_listをprintする関数
    def warshall_floyd(v_num, dist_lst):
        # 負の閉路を持つか
        negative_cycle_flag = False

        # 頂点iから頂点jへの経路と、頂点kを経由した場合の経路とを比較して
        # よりコストの合計が小さい方を配列に入れる動的計画法
        for k in range(v_num):
            for i in range(v_num):
                for j in range(v_num):
                    # i→k→jがつながっててしかもi→jルートよりもイケてるなら更新
                    if dist_lst[i][k] != INF and dist_lst[k][j] != INF:
                        if dist_lst[i][j] > dist_lst[i][k] + dist_lst[k][j]:
                            dist_lst[i][j] = dist_lst[i][k] + dist_lst[k][j]

        for v in range(v_num):
            # dist_lstに負の数が格納されているとは、
            # グラフが負の閉路を持つことを意味する
            if dist_lst[v][v] < 0:
                negative_cycle_flag = True

        return dist_lst

    H, W = map(int, input().split())
    # 頂点の数と辺の数
    v_num, e_num = 10, 100

    # 配列dist_lst[a][b]には頂点a,b間の辺のコストを入れておき、
    # a=bの時は0を、a,b間の辺が存在しないときはINFを入れておく。
    INF = 10 ** 20
    dist_lst = [[INF] * v_num for _ in range(v_num)]

    costs = [[i for i in list(map(int, input().split()))] for _ in range(10)]
    for s in range(10):
        for t in range(10):
            dist_lst[s][t] = costs[s][t]

    dist_lst = warshall_floyd(v_num, dist_lst)
    wall = [[i for i in list(map(int, input().split()))] for _ in range(10)]
    cnt = 0
    for h in range(H):
        for w in range(W):
            val = wall[h][w]
            if val != -1:
                cnt += dist_lst[val][1]
    print(cnt)


resolve()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    # 最短経路問題で使われるアルゴリズムの１つ。
    # グラフ上の全ての頂点間の最短経路を探す
    # 負の閉路（辺の重みの和が負になるような閉路）がない限り、負の辺があっても使える。

    # 負の閉路を持つ場合は'NEGATIVE CYCLE'を、そうでない場合には(i,j)成分に
    # 頂点iから頂点jへの最短経路の距離を格納するdist_listをprintする関数
    def warshall_floyd(v_num, dist_lst):
        # 負の閉路を持つか
        negative_cycle_flag = False

        # 頂点iから頂点jへの経路と、頂点kを経由した場合の経路とを比較して
        # よりコストの合計が小さい方を配列に入れる動的計画法
        for k in range(v_num):
            for i in range(v_num):
                for j in range(v_num):
                    # i→k→jがつながっててしかもi→jルートよりもイケてるなら更新
                    if dist_lst[i][k] != INF and dist_lst[k][j] != INF:
                        if dist_lst[i][j] > dist_lst[i][k] + dist_lst[k][j]:
                            dist_lst[i][j] = dist_lst[i][k] + dist_lst[k][j]

        for v in range(v_num):
            # dist_lstに負の数が格納されているとは、
            # グラフが負の閉路を持つことを意味する
            if dist_lst[v][v] < 0:
                negative_cycle_flag = True

        if negative_cycle_flag:
            print("NEGATIVE CYCLE")
        else:
            return dist_lst

    H, W = map(int, input().split())
    # 頂点の数と辺の数
    v_num, e_num = 10, 100

    # 配列dist_lst[a][b]には頂点a,b間の辺のコストを入れておき、
    # a=bの時は0を、a,b間の辺が存在しないときはINFを入れておく。
    INF = 10 ** 20
    dist_lst = [[INF] * v_num for _ in range(v_num)]

    costs = [[i for i in list(map(int, input().split()))] for _ in range(10)]
    for s in range(10):
        for t in range(10):
            dist_lst[s][t] = costs[s][t]

    dist_lst = warshall_floyd(v_num, dist_lst)
    wall = [[i for i in list(map(int, input().split()))] for _ in range(10)]
    cnt = 0
    for h in range(H):
        for w in range(W):
            val = wall[h][w]
            if val != -1:
                cnt += dist_lst[val][1]
    print(cnt)


resolve()

Submission status: Runtime Error

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

h,w = map(int,input().split())
d = np.zeros((10,10))
for i in range(10):
    a = list(map(int,input().split()))
    d[i] = a
#print(d)
def WF(b):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
WF(d)
#d = floyd_warshall(d)
L = []
for i in range(h):
    b = list(map(int,input().split()))
    L.append(b)
ans = 0
for i in range(h):
    for j in range(w):
        if L[i][j] == 1 or L[i][j] == -1:
            continue
        else:
            ans += d[L[i][j]][1]
print(int(ans))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
typedef long long ll;
#define MOD 1000000007
 
using namespace std;


int main(){
    int H,W;
    cin >> H >> W;
    int c[10][10];
    int cnt[10] = {0};
    int a;
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            cin >> c[i][j];
        }
    }
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cin >> a;
            if(a!=-1) cnt[a]++;
        }
        
    }
    
    for (int k = 0; k < 10; k++)
    {
        for (int i = 0; i < 10; i++)
        {
            for (int j = 0; j < 10; j++)
            {
                c[i][j] = min(c[i][j],c[i][k]+c[k][j]);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 10; i++)
    {
        ans += cnt[i]*c[i][1];
    }
    cout << ans << endl;
    return 0;
}

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

H, W = mi()
C = li2(10)
A = li2(H)

D = dp2(0, 10, 10)

for i in range(10):
    for j in range(10):
        D[i][j] = C[i][j]

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 abs(a[i][j]) != 1:
            ans += C[a[i][j]][1]

print(ans)

Submission status: Runtime Error

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path
from collections import defaultdict
h, w = map(int, input().split())
table = [list(map(int, input().split())) for _ in range(10)]
dd = defaultdict(int)
for _ in range(h):
    for x in map(int, input().split()):
        if x == -1:
            continue
        dd[x] += 1

trans_table = list(zip(*table))
scores = shortest_path(csr_matrix(trans_table), indices=1)

ans = 0
for k, v in dd.items():
    ans += int(scores[k])*v
print(ans)

Submission status: Runtime Error

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

for i in range(10**3-1):
    for i in range(10):
        for j in range(10):
            if i!=j:
                ll[i][j]=min(ll[i][j],min(ll[i][o]+tra[o][j] for o in range(10) if o!=i and o!=j))
ans=0
for i in range(h):
    for j in map(int,input().split()):
        if j==-1 or j==1:continue
        ans+=ll[j][1]
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
import math
class Graph:
    def __init__(self,v,w_e,w_v = None):
        super().__init__()
        self.v = v

        self.w_v = w_v
        self.w_e = [{} for _ in [0]*self.v]


        self.neighbor = [[] for _ in [0]*self.v]
        for a_i,b_i,w_i in w_e:
            self.w_e[a_i][b_i] = w_i#weight of edge
            self.neighbor[a_i].append(b_i)

    def dijkstra(self,v_n):
        d = [math.inf]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

def main():
    h,w = tuple([int(t)for t in input().split()])

    c = [[int(t) for t in input().split()]for _ in [0]*10]

    a = [[int(t) for t in input().split()]for _ in [0]*h]

    counter = [0]*10
    for a_i in a:
        for a_ij in a_i:
            if a_ij != -1:
                counter[a_ij]+=1

    w_e = []
    for i in range(10):
        for j in range(10):
            w_e.append((i,j,c[i][j]))
    
    g = Graph(10,w_e)

    routes = []
    for i in range(10):
        routes.append(g.dijkstra(i)[0])

    ans = 0
    for i in range(10):
        if i!=1:
            ans += routes[i][1]*counter[i]

    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
c = [[int(i) for i in input().split()] for _ in range(10)]
A = {i:0 for i in range(10)}
for _ in range(h):
  for i in input().split():
    A[int(i)] += 1
    

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

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

Submission status: Runtime Error

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
from scipy.sparse.csgraph import floyd_warshall
c = floyd_warshall(c)
ans = 0
for i in a:
    for j in i:
        if j!=-1: ans += c[j][1]
print(int(ans))

Submission status: Runtime Error

Solution code:

def search(start: int, visited: list, power: list, min_power: int, min_powers: int) -> int:
    minimum = 10**4
    if min_powers[start] != -1:
        return min_powers[start] + min_power
    if visited[1] == True:
        #print(f'{min_power=}')
        return min_power
    for i, v in enumerate(visited):
        if not v:
            visited[i] = True
            min_power += power[start][i]

            #min_powers[i] = search(i,visited,power,min_power,min_powers)
            minimum = min(minimum, search(i,visited,power,min_power,min_powers))

            visited[i] = False
            min_power -= power[start][i]
            #print(f'{minimum=}')
    return minimum


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

power = [[] for _ in range(10)]

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

world = [[] for _ in range(H)]

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

min_powers = [-1] * 10
visited = [False] * 10

#print(f'{power[8][4]=}')
for i in range(10):
    min_power = 0
    visited[i] = True
    min_powers[i] = search(i,visited,power,min_power,min_powers)
    visited[i] = False
    #visited = [False] * 10
for i in range(10):
    #pass
    print(f'{i=}, {min_powers[i]=}')
ans = 0
for wor in world:
    for w in wor:
        if w != -1:
            ans += min_powers[w]

print(ans)

Submission status: Runtime Error

Solution code:
aH,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: Runtime Error

Solution code:
h,w = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(9)]
li = [list(map(int,input().split())) for i in range(h)]

for i in range(9):
    for j in range(9):
        for k in range(9):
            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[i][j]
print(ans)

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
lis = [list(map(int,input().split())) for i in ragne(9)]
li = [list(map(int,input().split())) for i in range(h)]

for i in range(9):
    for j in range(9):
        for k in range(9):
            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[i][j]
print(ans)

Submission status: Runtime Error

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 = [math.inf] * 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: Runtime Error

Solution code:
# ABC79 D - Wall
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

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

C = floyd_warshall(C)  

cost = 0
for i in range(H):
    for a in A[i]:
        if a != -1:
            cost += C[a][1]

print(int(cost))

Submission status: Runtime Error

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):
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: Runtime Error

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: Runtime Error

Solution code:
dp=[[0 for j in range(10)] for i in range(10)]

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

for k in range(10):
    for i in range(10):
        for j in range(10):
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
c=0
for i in range(h):
    s=list(map(int,input().split()))
    for j in range(w):
        if s[j]==-1 or s[j]==1:
            continue
        else:
            c+=dp[s[j]][i]
print(c)

Submission status: Runtime Error

Solution code:
dp=[[0 for j in range(10)] for i in range(10)]
#print(dp)
h,w=map(int,input().split())
for i in range(10):
    s=list(map(int,input().split()))
    for j in range(10):
        dp[i][j]=s[j]

#print(dp)

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

#print(dp)
print(c)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

int main() {
  int H, W; cin >> H >> W;
  vector<vector<int>> G(10, vector<int>(10));
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) cin >> G.at(i).at(j);
  }
  vector<vector<int>> A(H, vector<int>(W));
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) cin >> A.at(i).at(j);
  }
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      for (int k = 0; k < 10; k++) {
        G.at(j).at(k) = min(G.at(j).at(k), G.at(j).at(i)+G.at(i).at(k));
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (A.at(i).at(j) != -1) ans += G.at(A.at(i).at(j)).at(1);
    }
  }
  cout << ans << endl;
}

Submission status: Runtime Error

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

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

wall = [0 for i in range(w)]

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

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

Submission status: Runtime Error

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

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

wall = [0 for i in range(w)]

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

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

Submission status: Runtime Error

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

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

wall = [0 for i in range(w)]

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
magialist=[]
datalist=[]
h,w=map(int,input().split())
#for i in range(10):
    #add=list(map(int,input().split()))
    #magialist.append(add)
add=list(map(int,input().split()))
for i in range(10):
    magialist.append(add)



for j in range(h):
    add1=list(map(int,input().split()))
    datalist.extend(add1)
 
storelist=[[[[] for i in range(10)] for i in range(10)] for i in range(10)]
    #わーシャルフロイド法
for i in range(10):
    for j in range(10):
            a=min(magialist[i][j],magialist[i][0]+magialist[0][j])
            storelist[0][i][j]=a
k=1
while k<=9:
    for i in range(10):
        for j in range(10):
                a=min(storelist[k-1][i][j],storelist[k-1][i][k]+storelist[k-1][k][j])
                storelist[k][i][j]=a
    k+=1

uselist=[]
                                                                                        
for j in range(10):
    uselist.append(storelist[9][j][1])
ans=0
for nums in range(h*w):
    
    for i in range(10):
        if datalist[nums]==-1:
            continue
        
        elif datalist[nums]==i:
            ans+=uselist[i]
print(ans)

Submission status: Runtime Error

Solution code:
magialist=[]
datalist=[]
h,w=map(int,input().split())
for i in range(10):
    add=list(map(int,input().split()))
    magialist.append(add)
for j in range(h):
    add1=list(map(int,input().split()))
    datalist.extend(add1)
storelist=[[[]*10]*10]*10
    #わーシャルフロイド法
def warsyaru(i,j,k):
    if k==0:
            return min(magialist[i][j],magialist[i][0]+magialist[0][j])
            storelist[i][j][0].append(min(magialist[i][j],magialist[i][0]+magialist[0][j]))
            
    elif k>=1:
        return min(storelist[i][j][k-1],storelist[i][k][k-1]+storelist[k][j][k-1])
        storelist[i][j][k].append(storelist[i][j][k-1],storelist[i][k][k-1]+storelist[k][j][k-1])
uselist=[]
for j in range(10):
    uselist.append(warsyaru(j,1,9))
ans=0
for nums in range(h*w):
    
    for i in range(10):
        if datalist[nums]==-1:
            continue
        
        elif datalist[nums]==i:
            ans+=uselist[i]
print(ans)

Submission status: Runtime Error

Solution code:
magialist=[]
datalist=[]
h,w=map(int,input().split())
for i in range(10):
    add=list(map(int,input().split()))
    magialist.append(add)
for j in range(h):
    add1=list(map(int,input().split()))
    datalist.extend(add1)
storelist=[[[]*10]*10]*10
    #わーシャルフロイド法
def warsyaru(i,j,k):
    if k==0:
            return min(magialist[i][j],magialist[i][0]+magialist[0][j])
            storelist[i][j][0].append(min(magialist[i][j],magialist[i][0]+magialist[0][j]))
            
    elif k>=1:
        return min(storelist[i][j][k-1],storelist[i][k][k-1]+storelist[k][j][k-1])
        storelist[i][j][k].append(storelist[i][j][k-1],storelist[i][k][k-1]+storelist[k][j][k-1])
uselist=[]
for j in range(10):
    uselist.append(warsyaru(j,1,9))
ans=0
for nums in range(h*w):
    for i in range(10):
    if datalist[num]=i
    ans+=uselist[i]
print(ans)

Submission status: Runtime Error

Solution code:
#%%
import copy 

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

d = copy.deepcopy(c)

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


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


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

print(ans)