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

    cost = [0 for _ in range(10)]
    for i in range(10):
        if i==1:
            continue
        else:
            flag = [0 for _ in range(10)] # 行ったところは1
            flag[i] = 1
            q = [[i,0,flag],] # 今いるとこ、今のコスト、行ったところ
            min_cost = c[i][1]
            while q != []:
                now, now_cost, now_flag = q.pop(0)
                if now==1:
                    if now_cost<min_cost:
                        min_cost = now_cost
                else:
                    for j in range(10):
                        if now_flag[j]==0 and now_cost+c[now][j]<min_cost:
                            next_flag = now_flag.copy()
                            next_flag[now] = 1
                            q.append([j,now_cost+c[now][j],next_flag])
            cost[i] = min_cost                            
    
    result = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == -1:
                result += 0
            else:
                result += cost[A[i][j]]
    return result
print(main())

Submission status: Accepted

Solution code:
import heapq
h, w = map(int, input().split())
cost = []

for i in range(10):
    c = list(map(int, input().split()))
    cost.append(c)
    
dist = [[float('inf') for _ in range(10)] for _ in range(10)]
for i in range(10):
    dist[i][i] = 0
    
for s in range(10):
    next_v = [[0, s]]
    
    while len(next_v):
        v = next_v[0][1]
        for i in range(10):
            if dist[s][i] > dist[s][v] + cost[v][i]:
                dist[s][i] = dist[s][v] + cost[v][i]
                heapq.heappush(next_v, [dist[s][i], i])
        heapq.heappop(next_v)
      
mp = 0
for i in range(h):
    a = list(map(int, input().split()))
    for t in range(w):
        if a[t] != -1 and a[t] != 1:
            mp += dist[a[t]][1]

print(mp)

Submission status: Accepted

Solution code:
from collections import Counter
H,W = map(int,input().split())

d = [list(map(int,input().split())) for i in range(10)]
for i in range(10):
    d[i][i] = 10**9 #inf
src = [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):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ctr = Counter()
for row in src:
    ctr.update(row)
ans = 0
for i in range(10):
    if i == 1: continue
    ans += ctr[i] * d[i][1]
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
C = [0]*10
for i in range(10):
    C[i] = list(map(int,input().split()))
A = [0]*H
for i in range(H):
    A[i] = 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):
    B = A[i]
    for b in B:
        if b > -1:
            Ans += C[b][1]
print(Ans)

Submission status: Accepted

Solution code:
MAX = 99999999


def solve(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])

    return dp


def m():
    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 for _ in range(10)]
    # dp = [[MAX] * 10 for _ in range(10)]
    c = solve(c)

    for a in A:
        for i in a:
            if i != -1:
                ans[i] += 1

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


print(m())

Submission status: Accepted

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

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

for l in range(h):
  tile = list(map(int, input().split()))
  for m in tile:
    if m != -1:
      ans += graph[m][1]

print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
c,A,s = [],[],0
for i in range(10):
    c.append(list(map(int,input().split())))
for i in range(H):
    A.append(list(map(int,input().split())))
for i in range(10):
    for j in range(10):
        for k in range(10):
            c[j][k] = min(c[j][k], c[j][i]+c[i][k])
for i in range(10):
    for j in range(H):
        s += A[j].count(i) * c[i][1]
print(s)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
c,A,s = [],[],0
for i in range(10):
    c.append(list(map(int,input().split())))
for i in range(H):
    A.append(list(map(int,input().split())))
for i in range(10):
    for j in range(10):
        for k in range(10):
            c[j][k] = min(c[j][k], c[j][i]+c[i][k])
for i in range(10):
    for j in range(H):
        s = s + A[j].count(i) * c[i][1]
print(s)

Submission status: Accepted

Solution code:
h,w = [int(i) for i in input().split()]

M = [[int(i) for i in input().split()] for j in range(10)]

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

ans = 0            
for i in range(h):
    a = [int(i) for i in input().split()]
    for j in a:
        if j == -1:
            continue
        else:
            ans += M[int(j)][1]

print(ans)

Submission status: Accepted

Solution code:
H, W = list(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 j in range(10):
        for i in range(10):
            c[j][i] = min(c[j][i], c[j][k] + c[k][i])

ans = 0
for aa in A:
    for a in aa:
        if a == -1:
            continue
        else:
            ans += c[a][1]

print(ans)

Submission status: Accepted

Solution code:
import collections
h,w = (int(i) for i in input().split())
c = [[int(i) for i in input().split()] for i in range(10)]
a = [[int(i) for i in 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][k]+c[k][j],c[i][j])
x,answer = [],0
for i in a: x+=i
y = collections.Counter(x)
for i in range(10):
	answer += y[i]*c[i][1]
print(answer)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
cost = [[0 for x in range(10)] for y in range(10)]
for i in range(10):
  tmp = input().split()
  for j in range(10):
  	cost[i][j] = int(tmp[j])
flg = False    
number = [0]*10
for k in range(H):
  tmp = input().split()
  for l in range(W):
    if int(tmp[l]) > -1:
      number[int(tmp[l])] +=1
      flg = True

def wf():
  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])
if flg:
	wf()
sum = 0
for z in range(10):
	sum += number[z]*cost[z][1]
print(sum)

Submission status: Accepted

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

def dijkstra(s):
  use=[0 for i in range(10)]
  d=[1000000000000 for j in range(10)]
  d[s]=0
  while True:
    v=-1
    for i in range(10):
      if use[i]==0 and (v==-1 or d[i]<d[v]):
        v=i
    if v==-1:
      break
    use[v]=1
    for j in range(10):
      d[j]=min(d[j],d[v]+C[v][j])
  return d[1]

ans=[0 for i in range(10)]
for i in range(10):
  ans[i]=dijkstra(i)

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

Submission status: Accepted

Solution code:
from queue import PriorityQueue

def bfs(num, c):
    ans=0
    queue=PriorityQueue()
    for i in range(len(c[num])):
        if num != i:
            queue.put_nowait((c[num][i], i))


    while not queue.empty():
        node=queue.get_nowait()
        if node[1] == 1:
            return node[0]
        else:
            for num in range(len(c[node[1]])):
                if num != node[1]:
                    queue.put_nowait((node[0]+c[node[1]][num], num))

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

for i in range(10):
    c.append([int(i) for i in input().split()])

for i in range(H):
    for n in input().split():
        num=int(n)
        if -1 != num and 1 != num:
            numList[num]+=1
ans=0
for i in range(len(numList)):
    if numList[i] != 0:
        ans+=bfs(i,c)*numList[i]

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

    c = []
    for i in range(10):
        c.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])

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

    print(sum(map(lambda i: c[i][1] if i >= 0 else 0, A)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

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

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

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

    print(sum(map(lambda i: c[i][1] if i >= 0 else 0, A)))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

for k in range(10):
    for i in range(10):
        for j in range(10):
            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 wall[i][j] != -1:
            ans += cost[wall[i][j]][1]

print(ans)

Submission status: Accepted

Solution code:
def Pto1(C):
    d = C.copy()
    for q in range(0,10):
        for i in range(0,10):
            for j in range(0,10):
                d[i][j] = min(d[i][j], d[i][q]+d[q][j])
    return [d[0][1],d[1][1],d[2][1],d[3][1],d[4][1],d[5][1],d[6][1],d[7][1],d[8][1],d[9][1]]

H,W = map(int,input().split(' '))
C = []
for i in range(0,10):
    cline = list(map(int,input().split(' ')))
    C.append(cline)
C1 = Pto1(C)
A = []
for j in range(0,H):
    aline = list(map(int,input().split(' ')))
    A.append(aline)
h=0
w=0
counter=[0]*10
while h<H:
    w=0
    while w<W:
        if A[h][w]>=0:
            counter[A[h][w]] += 1
        w+=1
    h+=1
Cmin = 0
for k in range(0,10):
    Cmin += C1[k]*counter[k]
print(int(Cmin))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
H, W = list(map(int, input().split()))

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

A = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
    line = list(map(int, input().split()))
    for j in range(W):
        A[i][j] = line[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])

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

print(total)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    h, w = list(map(int, input().split()))
    cost = {}
    for i in range(10):
        for j, c in enumerate(map(int, input().split())):
            cost[(i, j)] = 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)])
    
    cost[(-1, 1)] = 0
    
    print(sum([sum(map(lambda x: cost[(x, 1)], map(int, input().split()))) for i in range(h)]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import copy
import collections

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

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

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

mincost = {}
for i in range(10):
    mincost[i] = c[i][1]

copy_mincost = {}
while mincost != copy_mincost:
    copy_mincost = copy.deepcopy(mincost)
    for i in range(10):
        for j in range(10):
            if mincost[j] > mincost[i] + c[j][i]:
                mincost[j] = mincost[i] + c[j][i]

co = collections.Counter(A)
ans = 0

for i in range(0, 10):
    ans += co[i] * mincost[i]

print(ans)

Submission status: Accepted

Solution code:
import math
#d問をwf法で解く奴
INF=1000000000

cs=[[INF for i in range(10)]for j in range(10)]
nums=[0]*10 #各数字の個数

#cost=[[INF for i in range(10)]for j in range(10)] #cost[0][1]→0から1へのコスト


temp=list(map(int,input().split(" ")))
H=temp[0]
W=temp[1]
for i in range(10):
    temp=list(map(int,input().split(" ")))
    for j in range(10):
        cs[i][j]=temp[j] #i→jへのコスト

for i in range(H):
    temp=list(map(int,input().split(" ")))
    for j in range(W):
        if temp[j]!=-1:
            nums[temp[j]]+=1

for i in range(10): #経由するやつ
    for j in range(10): #始点
        for k in range(10): #終点
            cs[j][k]=min(cs[j][k],cs[j][i]+cs[i][k])

result=0
for i in range(10):
    result+=(nums[i]*cs[i][1])
print(result)

Submission status: Accepted

Solution code:
import math

def do():
    cs=[[0 for i in range(10)]for j in range(10)]
    #cs[0][1] → 0を1にか
    INF=10000000
    node_num=10
    unsearch=list(range(node_num)) #サーチが終わっていないノードのリスト us[0][1]==True →0と1をつなぐノードは未探索
    cos=[INF]*node_num #頂点1からのコスト cos[2][4] →
    cos[1]=0
    #preveious_nodes=[-1]*node_num
    nums=[0]*10 #各数字の個数

    temp=list(map(int,input().split(" ")))
    H=temp[0]
    W=temp[1]
    for i in range(10):
        temp=list(map(int,input().split(" ")))
        for j in range(10):
            cs[j][i]=temp[j]

    for i in range(H):
        temp=list(map(int,input().split(" ")))
        for j in range(W):
            if temp[j]!=-1:
                nums[temp[j]]+=1

    def get_target_min_index(min_index,distance,unsearch):
        start=0
        while True:
            index=distance.index(min_index,start)
            found=index in unsearch
            if found:
                return index
            else:
                start = index+1

    while len(unsearch)!=0:
        posible_min_distance=INF
        for node_index in unsearch:
            if posible_min_distance > cos[node_index]:
                posible_min_distance=cos[node_index]
        target_min_index=get_target_min_index(posible_min_distance,cos,unsearch)
        unsearch.remove(target_min_index)
        target_edge=cs[target_min_index] #あるVからの距離の一覧

        for index,route_dis in enumerate(target_edge):
             #Vからの総てのノードに対して計算
             if route_dis !=0:
                 if cos[index] > cos[target_min_index] + route_dis:
                     cos[index]=cos[target_min_index] + route_dis


    result=0
    for i in range(10):
        result+=(nums[i]*cos[i])
    print (result)

        


if __name__=="__main__":
    do()

Submission status: Accepted

Solution code:
# coding: utf-8
import queue
INF = 10000000

#初期化
G = []
kabe = []
H, W = map(int, input().split())

#入力
for i in range(10):
    G.append(list(map(int, input().split())))

for i in range(H):
    kabe.append(list(map(int, input().split())))

lenList = [INF for i in range(10)]

q = queue.PriorityQueue()

def dijkstra():
    global G
    global q
    global lenList
    
    x = q.get()
    #行ったことあるものは捨てる。
    if lenList[x[1]] != INF:
        return
    
    #間違いなく最短なので更新
    lenList[x[1]] = x[0]

    #行ったことないところをプッシュ
    for i in range(10):
        if lenList[i] == INF:
            q.put([x[0] + G[i][x[1]], i])

#初期値を入力して発火
q.put([0, 1])# [距離,現在地]
while not(q.empty()):
    dijkstra()

sum = 0

for i in range(H):
    for j in range(W):
        if kabe[i][j] != -1:
            sum += lenList[kabe[i][j]]

print(sum)

Submission status: Accepted

Solution code:
# coding: utf-8
import queue
INF = 10000000

q = queue.PriorityQueue()

#初期化
G = []
kabe = []
H, W = map(int, input().split())

#入力
for i in range(10):
    G.append(list(map(int, input().split())))

for i in range(H):
    kabe.append(list(map(int, input().split())))

lenList = [INF for i in range(10)]

def bfs():
    global G
    global q
    global lenList
    
    x = q.get()
    #行ったことあるものは捨てる。
    while lenList[x[1]] != INF:
        return
    
    #間違いなく最短なので更新
    lenList[x[1]] = x[0]

    #行ったことないところをプッシュ
    for i in range(10):
        if lenList[i] == INF:
            q.put([x[0] + G[i][x[1]], i])

#初期値を入力して発火
q.put([0, 1])
while not(q.empty()):
    bfs()

sum = 0

for i in range(H):
    for j in range(W):
        if kabe[i][j] != -1:
            sum += lenList[kabe[i][j]]

print(sum)

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)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
c=[[int(x) for x in input().split()] for _ in [0]*10]
a="".join([input() for _ in [0]*h])
nokori = [0,2,3,4,5,6,7,8,9]
while nokori:
    thiscost = 10**3
    for i in nokori:
        if c[i][1] <= thiscost:
            argmin = i
            thiscost = c[i][1]
    nokori.remove(argmin)
    for i in nokori:
        c[i][1] = min(c[i][1],c[i][argmin]+c[argmin][1])
c = c
ans = 0
for num in "023456789":
    ans += c[int(num)][1]*a.count(num)
print(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)]
ans=0

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

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

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, raw_input().split())
c = [map(int, raw_input().split()) for _ in range(10)]
A = [map(int, raw_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])

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq
INF = 1e9

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

n = 10
adj_matrix = []

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

Adj_list = defaultdict(set)

for i in range(n):
    for j in range(n):
        Adj_list[i].add((j, adj_matrix[i][j]))


def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)]
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u]+c, v))

    return d

ans = INF
t_dis = 0

table = {}
for i in range(n):
    table[i] = dijkstra(n, i)


t_dis = 0

for i in range(H):
    l = list(map(int, input().split()))
    for j in range(W):
        if l[j] != -1:
            t_dis += table[l[j]][1]
            
print(t_dis)

Submission status: Accepted

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

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

minimum_cost = [0 for i in range(10)]
for s in range(10):#s for start
    g =1 # g for goal
    md = [2000 for i in range(10)]#sからの最小距離
    md[s] = 0
    flag = [0 for i in range(10)]#確定フラグ
    while flag[g] != 1:

        mikakutei_min = min([md[j] for j in range(10) if flag[j]==0])
        for v in range(10):
            if (flag[v] == 0 and md[v] == mikakutei_min):
                flag[v] = 1
        for j in [j for j in range(10) if flag[j] == 0]:
            for i in [i for i in range(10) if flag[i] == 1]:
                if md[j] > md[i] + c[i][j]:
                    md[j] = md[i] + c[i][j]
    minimum_cost[s] = md[g]
        
#print(minimum_cost)                
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] != -1:
            ans += minimum_cost[A[i][j]]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import Counter
H, W = map(int, input().split())
c = [list(map(int, input().split())) for i in range(10)]
A = np.array([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):
			tmp_dist = c[i][k] + c[k][j]
			if c[i][j] > tmp_dist:
				c[i][j] = tmp_dist
print(sum(c[k][1] * v for k, v in Counter(A[A != -1]).items()))

Submission status: Accepted

Solution code:
import math
st=input().split()
H=int(st[0]);W=int(st[1])
c=[[0 for i in range(10)] for i in range(10)]
A=[[0 for i in range(W)]for i in range(H)]
for i in range(10):
    st=input().split()
    for j in range(10):
        c[i][j]=int(st[j])
for i in range(H):
    st=input().split()
    for j in range(W):
        A[i][j]=int(st[j])
def Dijkstra(s):
    d=[10000]*10
    d[s]=0
    Q=set(range(10))
    V=set(range(10))
    while(len(Q)>0):
        u=list(Q)[0]
        for i in Q:
            if d[i]<d[u]:
                u=i
        Q-={u}
        for v in V-{u}:
            if (d[v]>d[u]+c[u][v]):
                d[v]=d[u]+c[u][v]
    return d[1]
result=0
DD=[0]*10
for i in range(10):
    DD[i]=Dijkstra(i)
for i in range(H):
    for j in range(W):
        if A[i][j]!=-1:
            result+=DD[A[i][j]]
print(result)

Submission status: Accepted

Solution code:

inp = []
inp.append(raw_input())
for i in xrange(10 + int(inp[0].split(" ")[0])):
    inp.append(raw_input())
Size = inp[0]

Mml = [None, 0] + [None] * 8
Cij = [[0] * 10 for i in range(10)]
for i in xrange(10):
    for j, a in enumerate(map(int,inp[i + 1].split(" "))):
        Cij[i][j] = a
        #print a,
    #print

def sloveMm(n):
    global Mml
    if(Mml[n] != None):
        return Mml[n]
    Nmm = Cij[n][1]
    rourt = [[n, 0, Nmm,n]]
    while len(rourt) > 0:
        rl = len(rourt)
        new_rourt = []
        for rn in xrange(rl):
            r = rourt[rn]
            for i in xrange(10):
                if i != r[0]:
                    nm = r[1] + Cij[r[0]][i]
                    if nm < Nmm:
                        """if Mml[i] != None:
                            Mml[n] = nm + Mml[i]
                            return nm + Mml[i]"""
                        if i == 1:
                            #print r
                            Nmm = nm
                        new_rourt.append([i, nm, nm + Cij[i][1]] + r[3:] + [i] )
        rourt = new_rourt
    Mml[n] = Nmm
    return Nmm


NumberList = [0] * 10
for Ai in inp[11:]:
    #print Ai
    for A in Ai.split(" "):
        if A != "-1" and A != "":
            NumberList[int(A)] += 1

ans = 0
for i, n in enumerate(NumberList):
    if n > 0:
        ans += sloveMm(i) * n
        #print "AA",i,":",Cij[i][1],">>",Mml[i],"*", n
#print Mml
#print NumberList
print ans

Submission status: Accepted

Solution code:
def main():
    h,w=[int(i) for i in input().split()]
    c=[]
    for i in range(10):
        c.append([int(i) for i in input().split()])
    for i in range(10):
        for j in range(10):
            for k in range(10):
                c[j][k]=min(c[j][k],c[j][i]+c[i][k])
    ans=0
    for i in range(h):
        for j in [int(k) for k in input().split()]:
            if j!=1 and j!=-1:
                ans+=int(c[j][1])
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

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

    
def mini(S,dic,ans):
    if(S=={0,1,2,3,4,5,6,7,8,9}):
        return ans
    min_val=min(dic.values())
    for i in dic.keys():
        if dic[i]==min_val:
            S.add(i)
            pos=i
            break
    ans[pos]=dic.pop(pos)
    for i in dic.keys():
        dic[i]=min([dic[i],ans[pos]+C[i][pos]])
    return mini(S,dic,ans)

dic={}
for i in range(10):
    dic[i]=C[i][1]
M=mini(set(),dic,{})
M[-1]=0

ans=0
for i in range(H):
    for j in range(W):
        ans+=M[A[i][j]]
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc079/tasks/abc079_d
AC
"""
import sys
from sys import stdin
input = stdin.readline


def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dp[i][k] + dp[k][j] < dp[i][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]


def main(args):
    H, W = map(int, input().split())
    dp = []
    for i in range(10):
        temp = [int(x) for x in input().split()]
        dp.append(temp)

    warshallFloyd(10, dp)

    costs = [dp[i][1] for i in range(10)]
    total_cost = 0
    for _ in range(H):
        for i in map(int, input().split()):
            if i != -1:
                total_cost += costs[i]
    print(total_cost)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc079/tasks/abc079_d

"""
import sys
from sys import stdin
input = stdin.readline


def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dp[i][k] + dp[k][j] < dp[i][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]


def main(args):
    H, W = map(int, input().split())
    dp = []
    for i in range(10):
        temp = [int(x) for x in input().split()]
        dp.append(temp)

    warshallFloyd(10, dp)

    costs = [dp[i][1] for i in range(10)]
    total_cost = 0
    for h in range(H):
        itr = map(int, input().split())
        for i in itr:
            if i != -1:
                total_cost += costs[i]
    print(total_cost)


if __name__ == '__main__':
    main(sys.argv[1:])

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

#ワーシャルフロイドで最短距離行列を求める
def warshall(n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                cost[j][k] = min(cost[j][k], cost[j][i] + cost[i][k])

warshall(10)

ans = 0
for i in range(H):
    for j in range(W):
        use = pos[i][j]
        if use != -1:
            ans += cost[use][1]

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N = 10
H, W = input().split()
H = int(H)
W = int(W)
C = np.zeros((N, N), dtype=np.int)
for i in range(N):
    line = input().split()
    C[i, :] = list(map(int, line))

A = np.zeros((H, W), dtype=np.int)
for h in range(H):
    w = input().split()
    A[h, :] = list(map(int, w))

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

s = 0
for a in A.reshape(-1):
    if a >= 0:
        s += C[a, 1]
print(s)