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: Accepted

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)]
    d = []
    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 m in range(0,10):
        d.append(dijkstra(c,m))
    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:
                sum = sum + int(d[n][1])
    print(sum)

Submission status: Accepted

Solution code:
import sys
import numpy as np

def dijk(edge_list, start):
    checked = []
    queue = []
    dist = [100000 for i in range(10)]
    dist[start] = 0
    queue.append(start)
    while len(queue) != 0:
        index = np.argmin(list(map(lambda x: dist[x], queue)))
        node = queue.pop(index)
        checked.append(node)
        for child in edge_list[node]:
            dist[child[0]] = min(dist[child[0]], child[1] + dist[node])
            if (child[0] not in queue) and (child[0] not in checked):
                queue.append(child[0])
    return dist

H, W = list(map(int, sys.stdin.readline().strip().split(" ")))

edge_list = []
for i in range(10):
    l = list(map(int, sys.stdin.readline().strip().split(" ")))
    ll = []
    for j in range(10):
        ll.append((j, l[j]))
    edge_list.append(ll)

cost = []
for i in range(10):
    cost.append(dijk(edge_list, i)[1])

res = 0
for i in range(H):
    input_list = list(map(int, sys.stdin.readline().strip().split(" ")))
    res += np.sum(list(map(lambda x: 0 if (x == -1) else cost[x], input_list)))

print(res)

Submission status: Accepted

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

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

ans = 0
for i in range(H):
    row = list(map(int,input().split()))
    for a in row:
        if a < 0: continue
        ans += ds[a][1]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

import heapq
#thanks lethe2211!!
class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        >>> d = Dijkstra()
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0)
        [0, 2, 4, 5, 8] # 例えば，始点0から頂点3までの最短距離は5となる
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0, goal=4)
        [0, 2, 4] # 頂点0から頂点4までの最短経路は0 -> 2 -> 4となる
        '''
        num = len(adj)          # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
        
        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop
            
            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点を記録
                    
        if goal is not None:
            return self.get_distance(adj,goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))
    
    def get_distance(self, adj,goal, prev):
        '''
        始点startから終点goalまでの最短距離を求める
        '''
        path = self.get_path(goal, prev)
        dis = 0
        for i in range(len(path) - 1):
            dis += adj[path[i]][path[i+1]]
            
        return dis
      
wiz_power = []
keiro = Dijkstra()
for i in range(10):
    wiz_power.append(keiro.dijkstra(c,i,1))
    
sum_power = 0
for i in range(H):
    for j in range(W):
        if(A[i,j] != -1):
            sum_power += wiz_power[A[i,j]]
            
print(sum_power)

Submission status: Accepted

Solution code:
#def print_path(prev, cost):
#    for i in range(len(prev)):
#        print("%d, prev = %d, cost = %d" %  (i, prev[i], cost[i]))

def get_path(start, goal, prev):
    path = []
    now = goal
    path.append(now)
    while True:
        path.append(prev[now])
        if prev[now] == start: break
        now = prev[now]
    path.reverse()
    return path

def search(glaph, start, goal):
    MAX_VAL = 10000000
    g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    #print_path(prev, cost)
    return [get_path(start, goal, prev), cost[goal]]

N, M = list(map(int, input().split())) # 整数
c = []

for i in range(10):
    c.append(list(map(int, input().split())))

A = []
for i in range(N):
    A.append(list(map(int, input().split())))

truecost = [[0 for i in range(10)] for j in range(10)]
for i in range(10):
    for j in range(10):
        if i == j:
            truecost[i][j] = 0
        else:
            truecost[i][j] = search(c,i,j)[1]

ans=0
for i in range(N):
    for j in range(M):
        if A[i][j] == -1:
            continue
            
        ans = ans + truecost[A[i][j]][1]

print(ans)

Submission status: Accepted

Solution code:
h, w = [int(x) for x in raw_input().split()]
c = [[int(x) for x in raw_input().split()] for l in xrange(10)]
a = [[int(x) for x in raw_input().split()] for l in xrange(h)]
for t in xrange(10):
    for i in xrange(10):
        for j in xrange(10):
            for k in xrange(10):
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])
print sum([c[a[x][y]][1] for x in xrange(h) for y in xrange(w) if a[x][y] != -1])

Submission status: Accepted

Solution code:
def d_wall(H, W, C, A):
    # cost[i][j]には最終的に数字iからjに移行するための最小コストが格納される
    cost = [x[:] for x in C]

    # ワーシャルフロイド法で最小コストを計算
    for k in range(10):
        for i in range(10):
            for j in range(10):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    ans = 0
    # 壁の各数字ごとにコストの値を参照、和を取る
    for i in range(H):
        for j in range(W):
            if A[i][j] != -1:
                ans += cost[A[i][j]][1]  # 壁の数字から1へ移行するための最小コスト
    return ans

H,W = [int(i) for i in input().split()]
C = [[int(i) for i in input().split()] for j in range(10)]
A = [[int(i) for i in input().split()] for j in range(H)]
print(d_wall(H, W, C, A))

Submission status: Accepted

Solution code:
def main():
    H, W = list(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)]

    flag = True
    while flag:
        flag = False
        for i in range(10):
            for j in range(10):
                for k in range(10):
                    if c[i][k] + c[k][j] < c[i][j]:
                        c[i][j] = c[i][k] + c[k][j]
                        flag = True

    result = 0
    countNumber = []
    for i in range(10):
        if i != 1:
            a = sum([A[h].count(i) for h in range(H) if i in A[h]])
            countNumber.append(a)
            if countNumber[-1] != 0:
                result += c[i][1] * countNumber[-1]
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

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
temp=[0 for i in range(10)]
for i in range(H):
	for j in range(W):
		if A[i][j]==-1 or A[i][j]==1:
			continue
		else:
			if temp[A[i][j]]==0:
				temp[A[i][j]]=djk(A[i][j])
			sum+=temp[A[i][j]]

print sum

Submission status: Accepted

Solution code:
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

w, h = read_line(int, int)

c = []
for _ in range(10):
    c.append(read_line(int, int, int, int, int, int, int, int, int, int))

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

cost = 0
for _ in range(w):
    for a in read_line(*([int] * h)):
        if a >= 0:
            cost += c[a][1]

print(cost)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def dijkstra(adjList, s):
    num = len(adjList)
    dist = [float("INF") for i in range(10)]
    queue = []
    heappush(queue,(0,s))
    dist[s] = 0
    
    while queue != []:
        v_cost, v = heappop(queue)
        if dist[v] < v_cost:
            continue
        for u_cost, u in adjList[v]:
            if u != v and u_cost + dist[v] < dist[u]:
                dist[u] = u_cost + dist[v]
                heappush(queue, (dist[u], u))
    return dist


from sys import stdin
def IL():return list(map(int, stdin.readline().split()))

h,w = IL()
G = [[] for i in range(10)]

for i in range(10):
    l = IL()
    for j in range(10):
        G[i].append((l[j],j))


ans = 0
memo={}
for i in range(h):
    for i in IL():
        if abs(i) == 1:
          pass
        elif i in memo:
          ans += memo[i]
        else:
            t = dijkstra(G, i)[1] 
            memo[i] = t
            ans += t

print(ans)

Submission status: Accepted

Solution code:
#http://abc079.contest.atcoder.jp/
# -*- coding: utf-8 -*-

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

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

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

def min_cost(i,j,current,min_cost_current):
    if i == j: return current
    for index in range(10):
        if i == index: continue
        if current + mp[i][index] < min_cost_current:
            min_cost_current = min_cost(index,j,current+mp[i][index],min_cost_current)
    return min_cost_current


mp_min_cost =[]
for i in range(10):
    tmp = []
    for j in range(10):
        if i == j :
            tmp.append(0)
            continue

        min_cost_current = mp[i][j]
        if min_cost_current == sorted(mp[i])[1]:
            tmp.append(mp[i][j])
            continue

        # from i to j
        for index in range(10):
            if i == index: continue
            if mp[i][index] < min_cost_current:
                min_cost_current = min_cost(index,j,mp[i][index],min_cost_current)
        tmp.append(min_cost_current)
    mp_min_cost.append(tmp)

amount = 0
for i in wall:
    for j in i:
        if j == -1 or j == 1: continue
        amount += mp_min_cost[j][1]
print(amount)

Submission status: Accepted

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

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def d_wall(H, W, C, A):
    cost=C
    for k in range(10):
        for i in range(10):
            for j in range(10):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] != -1:
                ans += cost[A[i][j]][1]
    return ans

H,W = [int(i) for i in input().split()]
C = [[int(i) for i in input().split()] for j in range(10)]
A = [[int(i) for i in input().split()] for j in range(H)]
print(d_wall(H, W, C, A))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, raw_input().split())
c = [[0 for i in range(10)] for j in range(10)]
A = [[0 for i in range(W)] for j in range(H)]
for i in range(10):
    n = map(int, raw_input().split())
    for j in range(10):
        c[i][j] = n[j]
for i in range(H):
    n = map(int, raw_input().split())
    for j in range(W):
        A[i][j] = n[j]
        
def getDistance(start):
    if start == 1:
        return 0
    d = [1001 for i in range(10)]
    d[start] = 0
    prev = [-1 for i in range(10)]
    Q = set()
    for i in range(10):
        Q.add(i)
    while len(Q) != 0:
        min = 1001
        for i in range(10):
            if d[i] < min and i in Q:
                min = d[i]
                u = i
        Q.remove(u)
        for v in range(10):
            if d[v] > d[u] + c[u][v]:
                d[v] = d[u] + c[u][v]
                prev[v] = u
    return(d[1])



if __name__ == '__main__':
    D = [0 for i in range(10)]
    for i in range(10):
        D[i] = getDistance(i)
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] != -1:
                ans += D[A[i][j]]
    print(ans)

Submission status: Accepted

Solution code:
H, W = list(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)]

flag = True
while flag:
    flag = False
    for i in range(10):
        for j in range(10):
            for k in range(10):
                if c[i][k] + c[k][j] < c[i][j]:
                    c[i][j] = c[i][k] + c[k][j]
                    flag = True

result = 0
countNumber = []
for i in range(10):
    if i != 1:
        a = sum([A[h].count(i) for h in range(H) if i in A[h]])
        countNumber.append(a)
        if countNumber[-1] != 0:
            result += c[i][1] * countNumber[-1]
print(result)

Submission status: Accepted

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
mincost_list = []
for i in range(10):
    mincost_list.append(mincost(i,1))


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_list[board[h][w]]

print(need_magical_power)

Submission status: Accepted

Solution code:
from collections import deque
h, w = [int(x) for x in raw_input().split()]
c = [[int(x) for x in raw_input().split()] for line in xrange(10)]
a = [[int(x) for x in raw_input().split()] for line in xrange(h)]
for t in xrange(10):
    for i in xrange(10):
        for j in xrange(10):
            for k in xrange(10):
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])
cost = 0
for line in xrange(h):
    for col in xrange(w):
        if a[line][col] in [-1, 1]:
            continue
        else:
            cost += c[a[line][col]][1]
print cost

Submission status: Accepted

Solution code:
table = {1: 0}

def solve():
    global c, table
    queue = []
    for i in range(10):
        if i == 1:
            continue
        queue.append((c[i][1], i))
    while queue:
        queue.sort(reverse=True)
        a = queue.pop()
        if a[1] not in table:
            table[a[1]] = a[0]
            for i in range(10):
                if i == a[1]:
                    continue
                queue.append((a[0]+c[i][a[1]], i))

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

solve()

ans = 0
for i in range(H):
    for j in range(W):
        if 0 <= A[i][j] <= 9:
            ans += table[A[i][j]]

print(ans)

Submission status: Accepted

Solution code:
import copy
import sys
import numpy as np
import heapq
import time

from math import *
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

class warshall_floyd:
    def __init__(self):
        self.A = []

    def execute(self, adj_mat):
        self.A = copy.deepcopy(adj_mat)
        for k in range(len(self.A)):
            for i in range(len(self.A)):
                if self.A[i][k] < sys.maxint:
                    for j in range(len(self.A)):
                        if self.A[k][j] < sys.maxint:
                            self.A[i][j] = min(self.A[i][j], self.A[i][k] + self.A[k][j])


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W] = [int(input_raw[0]), int(input_raw[1])]
    dist_mat = [[0 for i in range(10)] for j in range(10)]
    for i in range(10):
        input_raw = read_func().strip().split()
        cost_list = (list(input_raw))
        for j in range(10):
            dist_mat[i][j] = int(cost_list[j])

    Warshall = warshall_floyd()
    Warshall.execute(dist_mat)

    score = 0;
    for i in range(H):
        input_raw = read_func().strip().split()
        raw_list = list(input_raw)
        for j in range(W):
            num = int(raw_list[j])
            if num >= 0:
                score += Warshall.A[num][1]

    print score;

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy
h, w = map(int, input().split())
c = []
for i in range(10):
    c.append(list(map(int, input().split())))
a = []
for i in range(h):
    a.append(list(map(int, input().split())))

for i in range(10):
    c_new = [[None for x in range(10)] for y in range(10)]
    for j in range(10):
        for k in range(10):
            c_new[j][k] = min(c[j][k], c[j][i] + c[i][k])
    c = copy.copy(c_new)

ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == -1:
            continue
        else:
            ans += c_new[a[i][j]][1]
print (ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra

H, W = map(int,input().split())
c = [[0 for i in range(10)] for j in range(10)]
for i in range(10):
    c[i] = list(map(int, input().split()))
t = dijkstra(c)
ans = 0
for i in range(H):
    for k in map(int, input().split()):
        if k == 1 or k == -1: continue
        ans += t[k][1]
print(int(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)]

path = [[0]*10 for i in range(10)]
for i in range(10):
    for j in range(10):
        path[i][j] = c[i][j]

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

min_route = []
for i in range(10):
    min_route.append(path[i][1])

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

ans = 0
for i in range(10):
    ans += wall_num[i] * min_route[i]

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python

from sys import stdin

def warshallfloyd(d):
  n = len(d)
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k] + d[k][j])

def solve(c, A):
  warshallfloyd(c)
  cost = 0
  for i in range(len(A)):
    for j in range(len(A[i])):
      if A[i][j] >= 0:
        cost += c[A[i][j]][1]
  return cost

def readints():
  return map(int, stdin.readline().split())

H, W = readints()
c = []
for i in range(10):
  c.append(readints())
A = []
for i in range(H):
  A.append(readints())
print(solve(c, A))

Submission status: Accepted

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

C = []
costs = {}
for i in range(10):
  C.append(list(map(int, input().split())))
  costs[i] = [float('inf')]*10
  costs[i][i] = 0
costs[-1] = [0]*10

for i in range(10):
  end = set()
  q = []
  heapq.heappush(q, (0, i))
  while len(q):
    c, k = heapq.heappop(q)
    if k == 1:
      break
    if costs[i][k] < c:
      continue
    end.add(k)
    for j in range(10):
      if j not in end:
        costs[i][j] = min(costs[i][j], c+C[k][j])
        heapq.heappush(q, (costs[i][j], j))

ans = 0
for i in range(H):
  ans += sum(map(lambda x: costs[int(x)][1], input().split()))

print(ans)

Submission status: Accepted

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

hw = raw_input()
hw = hw.split()
h,w = map(int,hw)

c = np.zeros([10,10],int)
for i in range(10):
    line = raw_input()
    line = line.split()
    c[i] = map(int,line)

#a = np.zeros([h,w],dtype=int)
#for i in range(h):
#    line = raw_input()
#    line = line.split()
#    a[i] = map(int,line)

suji_num = np.zeros([10],int)
for i in range(h):
    line = raw_input()
    line = line.split()
    line = map(int,line)
    for j in range(10):
        num = line.count(j)
        suji_num[j] += num

maryoku = np.zeros([10],int)

for i in range(10):
    maryoku[i] = c[i,1]

i = 1
while i < max(maryoku):
    #print maryoku
    for j in range(10):
        if maryoku[j] == i:
            for k in range(10):
                keiyum = c[k,j]+i
                if keiyum < maryoku[k]:
                    maryoku[k] = keiyum
    i += 1

ans = 0
for i in range(10):
    ans += suji_num[i] * maryoku[i]

print ans

Submission status: Accepted

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

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

A = [[0]*W for i in range(H)]

for i in range(H):
    a = list(map(int, input().split()))
    for j in range(W):
        A[i][j] = a[j]

for k in range(10):
    for i in range(10):
        for j in range(10):
                if i != j:
                    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 and A[i][j] != 1:
            ans += c[A[i][j]][1]
            
print(ans)

Submission status: Accepted

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

    # c から最小魔力テーブルの算出
    for k in range(10):
        for i in range(10):
            for j in range(10):
                c1 = c[i][j]
                c2 = c[i][k] + c[k][j]
                if c1 > c2:
                    c[i][j] = c2

    ans = 0
    for _ in range(H):
        for a in map(int, input().split()):
            if a != -1:
                ans += c[a][1]

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

A = [[0]*W for i in range(H)]

for i in range(H):
    a = list(map(int, input().split()))
    for j in range(W):
        A[i][j] = a[j]

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

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

Submission status: Accepted

Solution code:
import copy

h,w = map(int, raw_input().split(" "))

c = []

def search(num,c,prev,now,nopath):
  if num == 1:
    return now
  mindata = prev + c[num][1]
  for a in range(10):
    if a==1:continue
    if a in nopath:
      continue
    if (prev + c[num][a]) < mindata:
      np2 = copy.deepcopy(nopath)
      np2.append(a)
      q = search(a,c,prev + c[num][a],prev + c[num][1],np2)
      if q < mindata:
        mindata = q
  if mindata < now:
    return mindata
  else:
    return now

for a in range(0,10):
  c.append(map(int, raw_input().split(" ")))

wall = ""

for a in range(h):
  q = raw_input().split(" ")
  for x in q:
    if x != "-1":
      wall += x

#print "%r" % wall

# search num
num = [0]*10
for a in range(10):
  if str(a) in wall:
    num[a] = -1

# search minimum

for a in range(10):
  if a == 1:
    num[a] = 0
  if num[a] == -1:
    q = [a]
    num[a] = search(a,c,0,c[a][1],q)
  else:
    continue

ans = 0
for a in wall:
  ans += num[ int(a) ]
print ans

Submission status: Accepted

Solution code:


def f(C):
    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]:
                    C[i][j] = C[i][k] + C[k][j]

    return C


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

    f(C)

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

    res = 0

    for a in A:
        for i in a:
            if i < 0:
                continue
            res += C[i][1]

    print(res)
    return 0

if __name__ == '__main__':
    main()