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: Time Limit Exceeded

Solution code:
import heapq
import sys

H, W = map(int, input().split())
a = [[] for i in range(10)]
for i in range(10):
	c = [int(i) for i in input().split()]
	for j in range(10):
		a[i].append([c[j], j])
ans = 0
for i in range(H):
	A = [int(i) for i in input().split()]
	for j in A:
		if j == -1:
			continue
		b = [[0, j]]
		c = [False] * 10
		d = [sys.maxsize] * 10
		d[j] = 0
		while len(b):
			e = heapq.heappop(b)
			c[e[1]] = True
			for k in a[e[1]]:
				if c[k[1]]:
					continue
				if d[e[1]] + k[0] < d[k[1]]:
					d[k[1]] = d[e[1]] + k[0]
					heapq.heappush(b, [d[k[1]], k[1]])
		ans += d[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
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)]
ans = 0

def bfs(x):
    if x[-1]==1:
        global s
        buf = 0
        for i in range(len(x)-1):
            buf += c[x[i]][x[i+1]]
        s = min(s,buf)
    else:
        for i in range(10):
            if not i in x:
                bfs(x+[i])

for i in range(h):
    for j in range(w):
        if not a[i][j] in [1,-1]:
            s = 10**9
            bfs([a[i][j]])
            ans += s
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations 
h,w = map(int,input().split())
c = [[int(i) for i in input().split()] for _ in range(10)]
a = [[int(i) for i in input().split()] for _ in range(h)]
ans = 0
lst = [int(i) for i in range(10) if i != 1]
mp = [0]*10

for i in lst:
    mp[i] = c[i][1]
    for j in range(1,9):
        for k in permutations(lst,j):
            newlst = list(k)
            cnt = c[i][newlst[0]]
            for l in range(j-1):
                cnt += c[newlst[l]][newlst[l+1]]
            cnt += c[newlst[-1]][1]
            if cnt < mp[i]:
                mp[i] = cnt

for i in range(h):
    for j in range(w):
        if abs(a[i][j]) != 1:
            ans += mp[a[i][j]]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# h*wのマスにかかれているそれぞれの数字の位置は関係ないしどうでもいい
# それぞれの数がどれだけあるかに興味がある
# iから1に至る最小値を全探索 間に合うのか？ まあいけるやろ
h, w = map(int, input().split())
table = []
for _ in range(10):
    table.append(list(map(int, input().split())))

wall = {}
for _ in range(h):
    x = list(map(int, input().split()))
    for v in x:
        if v not in wall:
            wall[v] = 1
        else:
            wall[v] += 1


def rec(idx, cost, used):
    if idx == 1:
        return cost
    ret = 10 ** 10
    for i in range(10):
        if i in used:
            continue
        next_used = used[:]
        next_used.append(i)
        ret = min(ret, rec(i, cost + table[idx][i], next_used))
    return ret


arr = [0 for _ in range(10)]
for i in range(10):
    if i == 1:
        continue
    arr[i] = rec(i, 0, [i])

ans = 0
for k, v in wall.items():
    if k != -1 and k != 1:
        ans += arr[k] * v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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


to1 = [10**3 for i in range(10)]

nlist = [0] + [i for i in range(2,10)]

for i in range(1,10):
    for v in itertools.permutations(nlist,i):
        c = 0
        for j in range(i-1):
            c += cost[v[j]][v[j+1]]
        c += cost[v[i-1]][1]
        to1[v[0]] = min(to1[v[0]], c)

ans = 0
for h in range(H):
    for w in range(W):
        if A[h][w] != 1 and A[h][w] != -1:
            ans += to1[A[h][w]]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
H, W = map(int, input().split())
c = [list(map(int, input().split())) for i in range(10)]
A = [list(map(int, input().split())) for i in range(H)]
# cost = [[-1]*10 for i in range(10)]
# for j in range(10):
#     cost[j] = [[c[i][j], i] for i in range(10)]
cost = [-1]*10
cost[1] = 0

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


def search_cost(i, j, reached):
    # if dp[i][j] != -1:
    #     return dp[i][j]
    tmp_list = copy.copy(reached)
    tmp_list.append(i)
    ret = c[i][j]

    for k in range(10):
        if k == i or k == 1 or k in reached:
            continue
        else:
            tmp = c[i][k] + search_cost(k, j, tmp_list)
            ret = min(tmp, ret)
            if ret <= 2:
                break
            #print("i:"+str(i) + "k:" + str(k) + "j:"+str(j) + "=" + str(tmp))

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


for i in range(10):
    if i == 1:
        continue
    else:
        if c[i][1] <= 2:
            dp[i][1] = c[i][1]
            cost[i] = c[i][1]
        else:
            cost[i] = search_cost(i, 1, [])
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] != -1:
            ans += cost[A[i][j]]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calculate_mp(a, b, path, mp_sum):
    if a == b:
        return mp_sum
    cand = [k for k in range(10) if k not in path]
    mp_sum_list = []
    for c in cand:
        mp_sum_list.append(calculate_mp(c, b, path + [c], mp_sum + C[a][c]))
    return min(mp_sum_list)

H, W = [int(i) for i in input().split()]
C = []
for i in range(10):
    c = [int(i) for i in input().split()]
    C.append(c)
D = [0 for i in range(10)]
for i in range(10):
    D[i] = calculate_mp(i, 1, [i], 0)
cnt = 0
for i in range(H):
    A = [int(i) for i in input().split()]
    for a in A:
        if a != -1:
            cnt += D[a]
print(cnt)

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

INF = 10**18

def solve(h, w, c, a):
    v = list(range(10))
    dp = [INF] * 10
    for p in permutations(v):
        cost = 0
        for i in range(10):
            if p[i] == 1:
                break
            cost += c[p[i]][p[i+1]]
        dp[p[0]] = min(dp[p[0]], cost)
    ans = 0
    for r in range(h):
        for c in range(w):
            x = a[r][c]
            if x == -1:
                continue
            ans += dp[x]
    return ans

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)]
print(solve(h, w, c, a))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import*
h,w,*a=map(int,open(0).read().split())
print(int(sum(csgraph.dijkstra(csr_matrix([a[i*10:-~i*10]for i in range(10)]))[i][1]for i in a[100:]if i>=0)))

Submission status: Time Limit Exceeded

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

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

n_v = 10
inf = float('inf')

# コストテーブルの作成
from heapq import heappop, heappush
cost = dict() # コストテーブル
for i, j, k in mp2:
    cost[i] = cost.get(i, []) + [(j, k)]

total = 0
for i in range(len(a)):
    _a = a[i]
    for j in range(len(_a)):
        if _a[j] != -1:
            start = _a[j]

            d = [inf for i in range(n_v)] # 最短距離
            d[start] = 0

            q = [] # min-heap, (距離, 頂点)
            heappush(q, (d[start], start))
            while q:
                du, u = heappop(q) # 最短距離とその頂点
                if d[u] < du:
                    continue
                for v, weight in cost.get(u, []):
                    alt = du + weight
                    if d[v] > alt:
                        d[v] = alt
                        heappush(q, (alt, v))

            total += d[1]

print(total)

Submission status: Time Limit Exceeded

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

mp2 = []
for i in range(10):
    for j in range(10):
        mp2.append([i, j, c[i][j]])
n_v = 10
from heapq import heappop, heappush

total = 0
for i in range(len(a)):
    _a = a[i]
    for j in range(len(_a)):
        if _a[j] != -1:
            start = _a[j]

            # コストテーブルの作成
            inf = float('inf')
            d = [inf for i in range(n_v)] # 最短距離
            d[start] = 0
            prev = [None] * n_v # 経路をたどるときに使う
            cost = dict() # コストテーブル
            for i, j, k in mp2:
                cost[i] = cost.get(i, []) + [(j, k)]

            q = [] # min-heap, (距離, 頂点)
            heappush(q, (d[start], start))
            while q:
                # print(q, d, prev)
                du, u = heappop(q) # 最短距離とその頂点
                if d[u] < du:
                    continue
                for v, weight in cost.get(u, []):
                    alt = du + weight
                    if d[v] > alt:
                        d[v] = alt
                        prev[v] = u
                        heappush(q, (alt, v))

            total += d[1]

print(total)

Submission status: Time Limit Exceeded

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

def dfs(nv,vl,cost):
    if nv==1:
        return cost
    vl_ = vl.copy()
    vl_.append(nv)
    ret = []
    for i in range(10):
        if not i in vl_:
            ret.append(dfs(i,vl_,cost+c[nv][i]))
    return min(ret)
cost = []
for i in range(10):
    cost.append(dfs(i,[],0))
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j]!=-1:
            ans += cost[a[i][j]]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = (int(i) for i in input().split())
#m = [[int(i) for i in input().split] for i in range(1)]
m = []
for i in range(10):
    m.append(list(map(int, input().split())))
wall = []
for i in range(H):
	wall.append(list(map(int, input().split())))
# wall = [[int(i) for i in input().split] for i in range(H)]
cost = 0

def search(i,current_cost,min_cost):
	for j in range(10):
		if i != j:
			if current_cost + m[i][j] < min_cost:
				if j == 1:
					min_cost = current_cost + m[i][j]
					# return current_cost + m[i][j]
				else:
					tmp = search(j, current_cost + m[i][j], min_cost)
					if tmp < min_cost:
						min_cost = tmp
	return min_cost
for i in range(H):
	for j in range(W):
		if wall[i][j] != 1 and wall[i][j] != -1:
			cost += search(wall[i][j], 0, m[wall[i][j]][1])

print(cost)

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(graph,src):
    if graph is None:
        return None
    nodes = [i for i in range(len(graph))]
    visited=[]
    if src in nodes:
        visited.append(src)
        nodes.remove(src)
    else:
        return None
    distance={src:0}
    for i in nodes:
        distance[i]=int(graph[src][i])
    path={src:{src:[]}}
    k=pre=src
    while nodes:
        mid_distance=float('inf')
        for v in visited:
            for d in nodes:
                new_distance = int(graph[src][v])+int(graph[v][d])
                if new_distance < mid_distance:
                    mid_distance=new_distance
                    graph[src][d]=str(new_distance)
                    k=d
                    pre=v
        distance[k]=mid_distance
        path[src][k]=[i for i in path[src][pre]]
        path[src][k].append(k)
        visited.append(k)
        nodes.remove(k)
    return distance

if __name__=="__main__":
    sum = 0
    s = input().split(" ")
    x, y = s[0], s[1]
    c = [n for n in range(0,10)]
    matrix =[i for i in range(0,int(x))]*int(y)
    c[0] = list(input().split(" "))
    c[1] = list(input().split(" "))
    c[2] = list(input().split(" "))
    c[3] = list(input().split(" "))
    c[4] = list(input().split(" "))
    c[5] = list(input().split(" "))
    c[6] = list(input().split(" "))
    c[7] = list(input().split(" "))
    c[8] = list(input().split(" "))
    c[9] = list(input().split(" "))
    for i in range(0,int(x)):
        matrix[i] = input().split(" ")
        for j in range(0,int(y)):
            n = int(matrix[i][j])
            if n==-1:
                continue
            else:
                distance = dijkstra(c,n)
                sum = sum + int(distance[1])

    print(sum)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import heapq

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

#隣接リスト
c=[[] for i in range(10)]
for i in range(10):
	a=map(int,raw_input().split())
	for j in range(10):
		c[i].append(a[j])

#print c

A=[]
for i in range(H):
	A.append(map(int, raw_input().split()))
#print A


def djk(n):
	#開始位置
	Start=n

	#初期化
	d=[-1 for i in range(10)]
	d[Start]=0


	#優先度付きキューに[距離,頂点の番号]を格納する
	#スタート地点の頂点1には距離0を入れる
	q=[]
	heapq.heappush(q, [0,Start])

	while len(q)!=0:
		#距離が最小の頂点を取り出し
		l,u=heapq.heappop(q)
		for i,val in enumerate(c[u]):
			v=i
			l_u_v=val
			#print v, l_u_v
			if (d[v]>d[u]+l_u_v) or d[v]==-1:
				d[v]=d[u]+l_u_v
				heapq.heappush(q, [d[v],v])
	return d[1]


sum=0
for i in range(H):
	for j in range(W):
		if A[i][j]==-1 or A[i][j]==1:
			continue
		else:
			sum+=djk(A[i][j])

print sum

Submission status: Time Limit Exceeded

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

board = []
for h in range(H):
    board.append(list(map(int,input().split())))

def mincost(start,goal):
    queue = []
    queue.append((start,[],0))
    queue[0][1].append(start)
    mincost = 99999999999999999999999999999
    while len(queue) != 0:
        q = queue.pop(0)
        if q[0] == goal:
            if q[2] < mincost:
                mincost = q[2]
        else:
            for i in range(10):
                if i not in q[1]:
                    tq = q[1].copy()
                    tq.append(i)
                    if q[2]+MP[q[0]][i] < mincost:
                        queue.append((i,tq,q[2]+MP[q[0]][i]))
    return mincost

need_magical_power = 0
for h in range(H):
    for w in range(W):
        if board[h][w] == -1 or board[h][w] == 1:
            pass
        else:
            need_magical_power += mincost(board[h][w],1)

print(need_magical_power)

Submission status: Memory Limit Exceeded

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,1]
B = list(itertools.permutations(A))
N = [10**4+1]*10
N[1]= 0
ans = 0
for i in B:
    a = i[0]
    if a==1:
        continue
    ans = 0
    for j in range(1,10):
        ans +=c[i[j-1]][i[j]]
        if N[a]<ans:
          break
        if i[j]==1:
            N[a] = min(ans,N[a])
            break
        if N[i[j]]!=10**4+1:
            N[a] = min(ans+N[i[j]],N[a])
            break
ans = 0
for i in range(H):
    for j in range(W):
        if HW[i][j]!=-1:
            ans += N[HW[i][j]]
print(ans)

Submission status: Accepted

Solution code:
import sys

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

H, W = map(int, input().split())
inf = float("inf")
C = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(10)]
A = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(H)]
warshall_floyd()
res = 0
for row in A:
    for col in row:
        if col != -1:
            res += C[col][1]

print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import copy
from itertools import product
import sys
# from pprint import pprint
sys.setrecursionlimit(10**6)

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

min_ = [[10**4]*10 for i in range(10)]


# dq = [0, 0, set([0])]


# while(dq):
#     num, value, lists = dq.pop()
#     for i in range(10):
#         if i == 1:


def dfs(start=0, now=0, value=0):
    for i in range(10):
        value_tmp = value+map_[now][i]
        if value_tmp < min_[start][i]:
            min_[start][i] = value_tmp
            dfs(start, now=i, value=value_tmp)


for i in range(10):
    dfs(start=i, now=i, value=0)

count = [0]*10
for i in range(h):
    tmp = list(map(int, input().split()))
    for i in tmp:
        if i != -1:
            count[i] += 1

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

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
Cls = []
for i in range(10):
    Cls.append(list(map(int,input().split())))
for k in range(10):
    for i in range(10):
        for j in range(10):
            Cls[i][j] = min(Cls[i][j], Cls[i][k] + Cls[k][j])
costls = []
for i in range(10):
    costls.append(Cls[i][1])
numls = []
for i in range(H):
    numls += list(map(int,input().split()))
ans = 0
for i in range(H*W):
    if numls[i] == -1:
        continue
    ans += costls[numls[i]]
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


class Dijkstra:
    """Graph input:
    {
    node:{node:cost,node:cost...},
    node:{node:cost,node:cost...},
    ...
    }
    """

    def __init__(self, graph: dict, N: int):
        self.graph = graph
        self.costs = [float("inf")] * N

    def calculate(self, start):
        queue = list()

        # step1: push the start point into the priority queue
        self.costs[start] = 0
        heappush(queue, (0, start))  # (cost,node)

        while queue:
            # step2: get the minimum cost node from unfixed node and fix the cost
            cost_from_start, min_node = heappop(queue)

            # step3: update the direct connected nodes
            for link, cost in self.graph[min_node].items():
                if cost_from_start + cost < self.costs[link]:
                    self.costs[link] = cost_from_start + cost
                    heappush(queue, (self.costs[link], link))

        return self.costs


def main():
    h, w = input_int_list()

    G = defaultdict(dict)
    for i in range(10):
        line = input_int_list()
        for j in range(10):
            G[j][i] = line[j]

    # 1へ変換するコストをダイクストラ法で求める
    dijkstra = Dijkstra(G, 10)
    costs = dijkstra.calculate(1)

    cnts = defaultdict(int)
    for _ in range(h):
        line = input_int_list()
        for n in line:
            cnts[n] += 1

    ans = 0
    for k, v in cnts.items():
        if k == -1 or k == 1:
            continue
        ans += costs[k] * v

    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
class WarshallFloyd(object):
    def __init__(self):
        self.max_v = 10
        self.min_dist = [readInts() for _ in range(10)]
    def compute(self):
        for k,i,j in product(range(self.max_v), repeat = 3):
            # i -> j と i -> k -> j のうち、長くない方の距離
            self.min_dist[i][j] = min(self.min_dist[i][j], self.min_dist[i][k] + self.min_dist[k][j])
    def solve(self, n):
        if n == 1:
            return 0
        else:
            return self.min_dist[n][1]
h,w = readInts()
w = WarshallFloyd()
w.compute()
ans = 0
A = [readInts() for _ in range(h)]
for a in A:
    for i in a:
        if i == -1:
            continue
        ans += w.solve(i)
print(ans)

Submission status: Accepted

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

#d[i][j]は2頂点間i, j間の移動コストを格納, Vは頂点数
def warshall_floyd(d, V): 
	for k in range(V):
		for i in range(V):
			for j in range(V):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])

	return d #d[i][j]に頂点i, j間の最短距離を格納

d=warshall_floyd(C, 10)

ans=0
for _ in range(H):
	A=list(map(int, input().split()))
	for a in A:
		if a==-1:
			continue
		else:
			ans+=d[a][1]

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


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 main():
    H, W = MI()
    costs = []

    for i in range(10):
        cost_row = LI()
        costs.append(cost_row)

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

    ans = 0
    for _ in range(H):
        row = LI()
        for item in row:
            if item == -1:
                continue
            ans += costs[item][1]

    print(ans)


main()

Submission status: Accepted

Solution code:
import sys
import queue
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def ccc(start, goal, mat):
	open=queue.PriorityQueue()
	close=set()
	open.put((0, start))
	
	while True:
		cost, pos = open.get()
		#pa((cost,pos))
		if pos == 1:
			return cost
		if pos in close:
			continue
		for i in range(0,9+1):
			if i == pos:
				continue
			open.put((cost + mat[pos][i], i))
		else:
			close.add(pos)
	
	return -1

def main():
	#a = int(input())
	h, w = tin()
	#s = input()
	mm = [lin() for _ in range(10)]
	dist=dict()
	for i in range(0, 9+1):
		dist[i] = ccc(i,1,mm)
	dist[-1]=0
	
	ret=0
	for hi in range(h):
		al = lin()
		for v in al:
			ret += dist[v]
	return ret
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
numbers=[list(map(int,input().split())) for _ in range(10)]
A=[list(map(int,input().split())) for _ in range(H)]
cost=[[1001 for _ in range(10)] for _ in range(10)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            cost[i][j] = min(cost[i][j] , numbers[i][j] , numbers[i][k] + numbers[k][j] ,
                             cost[i][k] + cost[k][j] , numbers[i][k] + cost[k][j],
                             numbers[i][k] + cost[k][j])
ans=0
for a in A:
    for a_ in a:
        if a_ == 1 or a_ == -1:
            pass
        else:
            ans+=cost[a_][1]
print(ans)

Submission status: Accepted

Solution code:
def main():
	H, W = [int(x) for x in input().split(" ")]
	C = []
	for i in range(10):
		c = [int(m) for m in input().split(" ")]
		C.append(c)
	A = [0] * 10 # 0 ~ 9, idx = 10 -> -1
	for i in range(H):
		a = [int(m) for m in input().split(" ")]
		for j in range(W):
			if a[j] != -1:
				A[a[j]] += 1

	MP = [[C[i][1] for i in range(10)]] # MP[0] -> overwrite once, MP[1] -> overwrite twice
	for i in range(9):
		MP.append([min([(C[k][j] + MP[-1][j]) for j in range(10)]) for k in range(10)])

	minMP = [10000] * 10
	for i in range(len(MP)):
		for j in range(len(MP[i])):
			minMP[j] = min([minMP[j], MP[i][j]])
	print(sum([p * q for (p, q) in zip(A, minMP)]))

main()

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
dist = [[float("inf")] * 10 for _ in range(10)]
for i in range(10):
  cost = list(map(int,input().split()))
  for j in range(10):
    dist[i][j] = cost[j]
wall = []
for _ in range(h):
  wall.append(list(map(int,input().split())))
V = 10
for k in range(V):
  for i in range(V):
    for j in range(V):
      if dist[i][k]!=float("inf") and dist[k][j]!=float("inf"):
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ans = 0
for wa in wall:
  for wi in wa:
    if wi != -1:
      ans += dist[wi][1]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from scipy.sparse.csgraph import floyd_warshall

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


num_counter = Counter()
for i in range(H):
    num_counter += Counter(A[i])

if -1 in num_counter:
    del num_counter[-1]

if 1 in num_counter:
    del num_counter[1]

nei_graph = floyd_warshall(C, directed=True)

ans = 0
for k, v in num_counter.items():
    ans += nei_graph[k][1] * v

print(int(ans))

Submission status: Accepted

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

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

answer = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == -1:
            continue
        answer += C[A[i][j]][1]

print(answer)

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C&lang=ja
#https://dai1741.github.io/maximum-algo-2012/docs/shortest-path/

INF = (2*10**7)*100 + 1234567 #十分大きい値にすること!!!!!!

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

#Warshall–Floydで1に変える魔力を求めておく
for k in range(10):
    for i in range(10):
        for j in range(10):
            if c[i][j] > c[i][k] + c[k][j] and c[i][k]!=INF and c[k][j]!=INF:
                c[i][j] = c[i][k] + c[k][j]

ans = 0
for i in range(H):
    A_row = [int(e) for e in input().split()]
    for A in A_row:
        if A != -1:
            ans += c[A][1]
            
print(ans)

Submission status: Accepted

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][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]
print(ans)