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 8 s, 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

Solution (Python):
import heapq

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

Distance = [0] * 10

for p in range(10):
    q = p
    D = [float('inf')] * 10
    D[p] = 0
    HEAP = []
    d = 0
    c = 0
    while True:
        if p == 1:
            break
        for i in range(10):
            if D[i] == float('inf'):
                heapq.heappush(HEAP, (d + C[p][i], i))
        d, p = heapq.heappop(HEAP)
        D[p] = d
    Distance[q] = d
print(
    sum([
        sum([Distance[int(_)] for _ in input().split() if int(_) > -1])
        for _ in range(H)
    ]))

Solution (Python):
H, W = map(int, input().split())
C = [list(map(int, input().split())) for i in range(10)]
G = [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 row in G:
    for x in row:
        if x >= 0:
            ans += C[x][1]

print(ans)

Solution (Python):
def warshall_floyd(graph):
    num_v = len(graph)
    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    return graph


h, w = map(int, input().split())
route = []

for i in range(10):
    S = list(map(int, input().split()))
    route.append(S)
graph = warshall_floyd(route)
result = 0
for i in range(h):
    A = list(map(int, input().split()))
    for a in A:
        if a != -1:
            result += graph[a][1]
print(result)

Solution (Python):

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



point = [C[i][1] for i in range(10)] 
way = [[i,1] for i in range(10)] 



update = True
while update:
    update = False
    for i in range(10):
        for j in range(10):
            if i==j: continue
            
            if  C[i][j]+point[j]<point[i]:
                
                point[i] = C[i][j] + point[j] 
                way[i].remove(way[i][-1])
                way[i] = [i]+way[j]
                update = True
                
    
    
    


count = [0 for i in range(10)] 
for i in range(H):
    for j in range(W):
        if A[i][j]>=0: count[A[i][j]]+=1

sum = 0
for i in range(10): sum += count[i]*point[i]
print(sum)

Solution (Python):
import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist

h, w = map(int, input().split())
adj = [[] for _ in range(10)]
for i in range(10):
    c = list(map(int, input().split()))
    for j in range(10):
        adj[i].append((c[j], j))
shortest = []
for i in range(10):
    shortest.append(dijkstra(adj, 10, i)[1])
ans = 0
for i in range(h):
    a = list(map(int, input().split()))
    for j in a:
        if j != -1:
            ans += shortest[j]
print(ans)

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

for i in range(10):
    for j in range(10):
        if i == j:
            continue
        for k in range(10):
            if i == k or j == k:
                continue
            tmp = c[j][i] + c[i][k]
            if c[j][k] > tmp:
                
                c[j][k] = tmp

res = 0
for _ in range(H):
    for i in input().split():
        i = int(i)
        if i == -1:
            continue
        res += c[i][1]
print(res)

Solution (Python):
h,w = map(int,input().split())
dp=[list(map(int,input().split())) for i in range(10)]
for i in range(10):
    for j in range(10):
        for k in range(10):
            dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k])
ans = 0
for i in range(h):
    a = list(map(int,input().split()))
    for j in a:
        if j >= 0:
            ans +=dp[j][1]
print(ans)

Solution (Python):

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

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

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

res = 0
for _ in range(h):
    for a in map(int, input().split()):
        if a>=0:
            res += c[a][1]
print(res)

Solution (Python):
import heapq

H,W = (int(i) for i in input().split())
C = []
for i in range(10):
    C.append( [int(j) for j in input().split()] )
SU = []
for i in range(H):
    SU += [int(j) for j in input().split()]

def Dijkstra(graph, start):
    N = 10
    d = {}
    prev = {}
    for i in range(N):
        prev[i] = None
        if i == start:
            d[i] = 0
        else:
            d[i] = float('inf')
    Q = []
    heapq.heappush(Q, (0, start))
    while Q:
        d_u, u = heapq.heappop(Q)
        if d[u] < d_u:
            continue
        for i in range(N):
            if graph[i][u]:
                temp = d_u + graph[i][u]
                if d[i] > temp:
                    d[i] = temp
                    prev[i] = u
                    heapq.heappush(Q, (d[i], i))
    return (d, prev)

def saitan(start, goal, d, prev):
    temp = goal
    res = [goal]
    while True:
        res.append(prev[temp])
        if prev[temp] == start:
            break
        else:
            temp = prev[temp]
    return res

d, prev = Dijkstra(C, 1)

res = 0
for i in SU:
    if i == -1:
        pass
    else:
        res += d[i]

print(res)

Solution (Python):

from pprint import pprint
from collections import defaultdict
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)]

dist = floyd_warshall(c, directed=True)

A_cnt = defaultdict(int)
for h in range(H):
    for w in range(W):
        if A[h][w] != -1 and A[h][w] != 1:
            A_cnt[A[h][w]] += 1

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

print(int(ans))

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush

h, w = map(int, input().split())
c = []
for i in range(10):
    c.append([int(m) for m in input().split()])
a = []
for i in range(h):
    a.append([int(m) for m in input().split()])
dist = []
for i in range(10):
    for j in range(10):
        dist.append([i, j, c[i][j]])

class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

inputs = dist

g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)
    
spdi = {}
for i in range(10):
    d = Dijkstra(g, i)
    sp = format(d.shortest_distance(1))
    spdi[i] = int(sp)



ncdi = {}
ncdi = defaultdict(int)
for i in range(h):
    for j in range(w):
        ncdi[a[i][j]] += 1
count = 0
for i in range(10):
    count += spdi[i] * ncdi[i]
print(count)

Solution (Python):
H,W = map(int,input().split())
ds = [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):
            ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j])
ans = 0
for row in A:
    for a in row:
        if a < 0: continue
        ans += ds[a][1]
print(ans)

Solution (Python):
from heapq import *
from collections import Counter
H, W = map( int, input().split())
C = [ list( map( int, input().split())) for _ in range(10)]
A = [ list( map( int, input().split())) for _ in range(H)]
N = [0]*10
for i in range(H):
    CA = Counter(A[i])
    for j in range(10):
        N[j] += CA[j]
L = [(0,1)]
V = [-1]*10
while L:
    d, v = heappop(L)
    if not V[v] == -1:
        continue
    V[v] = d
    for i in range(10):
        if V[i] == -1:
            heappush(L, (d+C[i][v], i))
ans = 0
for i in range(10):
    ans += V[i]*N[i]
print(ans)

Solution (Python):
H, W=map(int,input().strip().split(' '))

def w_f():
    cost=[]
    for i in range(10):
        cost.append(list(map(int,input().strip().split(' '))))

    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])
    return cost
    
d=w_f()
ans=0
for i in range(H):
    a=list(map(int,input().strip().split(' ')))
    for j in a:
        if j!=-1:
            ans+=d[j][1]
print(ans)

Solution (Python):
H, W=map(int,input().strip().split(' '))

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

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):
    a=list(map(int,input().strip().split(' ')))
    for j in a:
        if j!=-1:
            ans+=cost[j][1]
print(ans)

Solution (Python):
import heapq
H, W = map(int, input().split())
C = [[int(i) for i in input().split()] for j in range(10)]

MinCost = [10000 for i in range(10)]
MinCost[1] = 0
Fin = [False for i in range(10)]
Fin[1] = True
Q = []
heapq.heappush(Q, (0, 1))
while Q:
    nowCost, nowNode = heapq.heappop(Q)
    Fin[nowNode] = True
    for i in range(10):
        if i != nowNode and Fin[i] == False:
            if MinCost[i] > nowCost + C[i][nowNode]:
                MinCost[i] = nowCost + C[i][nowNode]
                heapq.heappush(Q, (nowCost + C[i][nowNode], i))

Total = 0
for i in range(H):
    A = [int(i) for i in input().split()]
    for a in A:
        if a >= 0:
            Total += MinCost[a]
print(Total)

Solution (Python):
def main():
    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)]

    minimum_cost = [float("inf")] * 10
    minimum_cost[1] = 0
    pattern = [{
        "via": 1,
        "cost": 0
    }]
    while len(pattern):
        p = pattern.pop(0)
        via = p["via"]
        cost = p["cost"]
        for i in range(10):
            nextcost = cost + c[i][via]
            if nextcost < minimum_cost[i]:
                minimum_cost[i] = nextcost
                pattern.append({"via": i, "cost": nextcost})

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


if __name__ == "__main__":
    main()

Solution (Python):
H,W=map(int,input().split())
c=[[int(i) for i in input().split()] for i in range(10)]
Points=[]
for i in range(0,10):
  if i==1:
    Points.append(0)
  else:
    Roots=[[i]]
    Roots_finished=[]
    for R in Roots:
      for j in range(10):
        if R[-1]==1:
          Roots_finished.append(R)
          break
        elif j in R:
          pass
        elif j==1:
          R_kari=list(R)
          R_kari.append(1)
          Roots.append(R_kari)
        elif c[R[-1]][j]<c[R[-1]][1]:
          R_kari=list(R)          
          R_kari.append(j)
          Roots.append(R_kari)
    S=1000000000000
    for r in Roots_finished:
      S_kari=0
      j=r[0]
      for i in r:
        S_kari+=c[j][i]
        j=i
      if S>S_kari:
        S=S_kari
    Points.append(S)
Magic_Power=0
for i in range(H):
  for j in input().split():
    if int(j)==-1:
      j=1
    Magic_Power+=Points[int(j)]
print(Magic_Power)

Solution (Python):



import sys
fin = sys.stdin.readline
from copy import deepcopy


def warshall_floyd(w):
    num_vertices = len(w)
    dp = deepcopy(w)
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp


H, W = [int(elem) for elem in fin().split()]
c_list = [[int(elem) for elem in fin().split()] for _ in range(10)]
assert len(c_list[0]) == 10

A_list = [[int(elem) for elem in fin().split()] for _ in range(H)]
assert len(A_list[0]) == W

total_cost = 0
min_costs = warshall_floyd(c_list)
for A_row in A_list:
    for A in A_row:
        if A != -1 and A != 1:
            total_cost += min_costs[A][1]

print(total_cost)

Solution (Python):
import sys
fin = sys.stdin.readline
from copy import deepcopy


def warshall_floyd(w):
    num_vertices = len(w)
    dp = deepcopy(w)
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp


H, W = [int(elem) for elem in fin().split()]
c_list = [[int(elem) for elem in fin().split()] for _ in range(10)]
assert len(c_list[0]) == 10

A_list = [[int(elem) for elem in fin().split()] for _ in range(H)]
assert len(A_list[0]) == W

total_cost = 0
min_costs = warshall_floyd(c_list)
for A_row in A_list:
    for A in A_row:
        if A != -1 and A != 1:
            total_cost += min_costs[A][1]

print(total_cost)

Solution (Python):

import queue
from heapq import heappush, heappop

class Graph:

    INF = float('inf')
    
    def __init__(self,v_num,is_directed = False):
        self.is_directed = is_directed
        self.v_num = v_num
        self.E = []
        self.v_s_list = [[] for i in range(self.v_num)]
        
    def appendEdge(self,v1,v2,weight=1):
        if max(v1,v2,self.v_num-1)>=self.v_num or min(v1,v2)<0:
            print("ERROR: The vertex ID is wrong.")
            return False

        self.E.append([v1,v2,weight])
        
        if self.is_directed:
            self.v_s_list[v1].append([v2,weight])
        else:
            self.v_s_list[v1].append([v2,weight])
            self.v_s_list[v2].append([v1,weight])
        
        
    def BFS(self,v,usage="SSSP"):
        is_processed = [False for i in range(self.v_num)]
        distance_list = [Graph.INF for i in range(self.v_num)]
        Q = queue.Queue()
        Q.put(v)
        is_processed[v]=True
        distance_list[v] = 0
        while not Q.empty():
            v1 = Q.get()
            for v2 in self.v_s_list[v1]:
                if not is_processed[v2[0]]:
                    is_processed[v2[0]] = True
                    distance_list[v2[0]] = min(distance_list[v1]+1,distance_list[v2[0]])
                    Q.put(v2[0])
        if usage=="SSSP":
            return distance_list
        elif usage=="ConnectedComponent":
            cc_list = []
            for i in range(self.v_num):
                if is_processed[i]:
                    cc_list.append(i)
            return cc_list

    def getSSSPwithBFS(self,v):
        return self.BFS(v,"SSSP")
        
    def getConnectedComponent(self,v):
        return self.BFS(v,"ConnectedComponent")
        
    def getSSSPwithBellmanFord(self,v):
        distance_list = [Graph.INF for i in range(self.v_num)]
        distance_list[v] = 0
        pre_list = [None for i in range(self.v_num)]

        for i in range(self.v_num-1):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if distance_list[v2] > distance_list[v1] + d:
                    distance_list[v2] = distance_list[v1] + d
                    pre_list[v2] = v1
                    
        negative_loop_list = [False for i in range(self.v_num)]
        
        for i in range(self.v_num):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if d + distance_list[v1] < distance_list[v2]:
                    distance_list[v2] = d + distance_list[v1]
                    pre_list[v2] = v1
                    negative_loop_list[v2] = True
        
        return distance_list, pre_list, negative_loop_list

    def getSSSPwithDijkstra(self,v):
        distance_list = [Graph.INF for i in range(self.v_num)]
        distance_list[v] = 0
        pre_list = [None for i in range(self.v_num)]
        
        PQ = []
        for i in range(self.v_num):
            heappush(PQ,(distance_list[i],i))
        while len(PQ)>0:
            d,v1 = heappop(PQ)
            for v2 in self.v_s_list[v1]:
                if distance_list[v2[0]] > d + v2[1]:
                    distance_list[v2[0]] = d + v2[1]
                    pre_list[v2[0]] = v1
                    heappush(PQ,(distance_list[v2[0]],v2[0]))
        return distance_list,pre_list
    
H,W=list(map(int,input().split()))
C = []
for i in range(10):
    C.append(list(map(int,input().split())))

G = Graph(10,True)

for i in range(10):
    for j in range(10):
        if i!=j:
            G.appendEdge(i,j,C[i][j])

dto1 = []
for i in range(10):
    distance_list, pre_list, negative_loop_list=G.getSSSPwithBellmanFord(i)
    dto1.append(distance_list[1])
cost = 0
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        if A[j]!=-1:
            cost+=dto1[A[j]]
            
print(cost)

Solution (Python):

import queue
from heapq import heappush, heappop

class Graph:

    INF = float('inf')
    
    def __init__(self,v_num,is_directed = False):
        self.is_directed = is_directed
        self.v_num = v_num
        self.E = []
        self.v_s_list = [[] for i in range(self.v_num)]
        
    def appendEdge(self,v1,v2,weight=1):
        if max(v1,v2,self.v_num-1)>=self.v_num or min(v1,v2)<0:
            print("ERROR: The vertex ID is wrong.")
            return False

        self.E.append([v1,v2,weight])
        
        if self.is_directed:
            self.v_s_list[v1].append([v2,weight])
        else:
            self.v_s_list[v1].append([v2,weight])
            self.v_s_list[v2].append([v1,weight])
        
        
    def BFS(self,v,usage="SSSP"):
        is_processed = [False for i in range(self.v_num)]
        distance_list = [Graph.INF for i in range(self.v_num)]
        Q = queue.Queue()
        Q.put(v)
        is_processed[v]=True
        distance_list[v] = 0
        while not Q.empty():
            v1 = Q.get()
            for v2 in self.v_s_list[v1]:
                if not is_processed[v2[0]]:
                    is_processed[v2[0]] = True
                    distance_list[v2[0]] = min(distance_list[v1]+1,distance_list[v2[0]])
                    Q.put(v2[0])
        if usage=="SSSP":
            return distance_list
        elif usage=="ConnectedComponent":
            cc_list = []
            for i in range(self.v_num):
                if is_processed[i]:
                    cc_list.append(i)
            return cc_list

    def getSSSPwithBFS(self,v):
        return self.BFS(v,"SSSP")
        
    def getConnectedComponent(self,v):
        return self.BFS(v,"ConnectedComponent")
        
    def getSSSPwithBellmanFord(self,v):
        distance_list = [Graph.INF for i in range(self.v_num)]
        distance_list[v] = 0
        pre_list = [None for i in range(self.v_num)]

        for i in range(self.v_num-1):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if distance_list[v2] > distance_list[v1] + d:
                    distance_list[v2] = distance_list[v1] + d
                    pre_list[v2] = v1
                    
        negative_loop_list = [False for i in range(self.v_num)]
        
        for i in range(self.v_num):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if d + distance_list[v1] < distance_list[v2]:
                    distance_list[v2] = d + distance_list[v1]
                    pre_list[v2] = v1
                    negative_loop_list[v2] = True
        
        return distance_list, pre_list, negative_loop_list

    def getSSSPwithDijkstra(self,v):
        distance_list = [Graph.INF for i in range(self.v_num)]
        distance_list[v] = 0
        pre_list = [None for i in range(self.v_num)]
        
        PQ = []
        for i in range(self.v_num):
            heappush(PQ,(distance_list[i],i))
        while len(PQ)>0:
            d,v1 = heappop(PQ)
            for v2 in self.v_s_list[v1]:
                if distance_list[v2[0]] > d + v2[1]:
                    distance_list[v2[0]] = d + v2[1]
                    pre_list[v2[0]] = v1
                    heappush(PQ,(distance_list[v2[0]],v2[0]))
        return distance_list,pre_list
    
H,W=list(map(int,input().split()))
C = []
for i in range(10):
    C.append(list(map(int,input().split())))

G = Graph(10,True)

for i in range(10):
    for j in range(10):
        if i!=j:
            G.appendEdge(i,j,C[i][j])

dto1 = []
for i in range(10):
    distance_list, pre_list, negative_loop_list=G.getSSSPwithBellmanFord(i)
    dto1.append(distance_list[1])
cost = 0
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        if A[j]!=-1:
            cost+=dto1[A[j]]
            
print(cost)

Solution (Python):
h, w = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
p_min = []
for i in range(10):
    p = c[i]
    for j in range(10):
        pp = p
        for k in range(10):
            for l in range(10):
                pp[k] = min(pp[k], p[l] + c[l][k])
        p = pp
    p_min.append(p[1])
a = [list(map(int, input().split())) for _ in range(h)]
ans = 0
for i in range(10):
    count = 0
    for j in range(h):
        count += a[j].count(i)
    ans += count * p_min[i]
print(ans)

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
import heapq
h,w = inpl()
edge = [] 
inf = float('inf')
for i in range(10):
    edge.append(inpl())
Q = [[inf for _ in range(10)] for _ in range(10)]

for i in range(10):
    decided = [False for _ in range(10)]
    H = []
    Q[i][i] = 0
    heapq.heappush(H,(0,i))
    for _ in range(10):
        while True:
            k = heapq.heappop(H)
            k = k[1]
            if not decided[k]:
                decided[k] = True
                break
        for j in range(10):
            if decided[j]:
                continue
            Q[i][j] = min(Q[i][k] + edge[k][j], Q[i][j])
            heapq.heappush(H,(Q[i][j],j))
ct = [0 for _ in range(11)]
for i in range(h):
    A = inpl()
    for j in range(w):
        ct[A[j]] += 1
ans = 0
for i in range(10):
    ans += ct[i]*Q[i][1]
print(ans)

Solution (Python):
def search_min_cost(nums, prev_num, min_cost, cost, c):
    _last_min_cost = min_cost
    if len(nums) != 0:
        _min_cost = cost + c[prev_num][1]
        if min_cost < _min_cost:
            _min_cost = min_cost
        for i in nums:
            _nums = nums[:]
            _nums.remove(i)
            next_cost = cost + c[prev_num][i]
            if _min_cost <= next_cost:
                if _min_cost < _last_min_cost:
                    _last_min_cost = _min_cost
            else:
                '''
                if prev_num == 8:
                    print(_nums, i, _min_cost, next_cost)
                if prev_num == 4 and i == 9:
                    print(_nums, i, _min_cost, next_cost)
                '''
                m = search_min_cost(
                    _nums, i, _min_cost, next_cost, c)
                if m < _last_min_cost:
                    _last_min_cost = m
    else:
        m = cost + c[prev_num][1]
        if m < _last_min_cost:
            _last_min_cost = m
    return _last_min_cost


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)]
min_cost_map = {}
min_cost_map[1] = 0

nums = [0, 2, 3, 4, 5, 6, 7, 8, 9]
for i in nums:
    _nums = nums[:]
    _nums.remove(i)
    min_cost_map[i] = search_min_cost(_nums, i, 1001, 0, c)

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

Solution (Python):
H, W = map(int, input().split())
C = [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):
            C[i][j] = min(C[i][j], C[i][k] + C[k][j])

ans = 0
for h in range(H):
    A = list(map(int, input().split()))
    for a in A:
        if a >= 0:
            ans += C[a][1]

print(ans)

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

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




n = 10
dp = [[1000 for _ in range(n)] for _ in range(n)]

for i in range(n):
    dp[0][i] = c[i][1]



for i in range(1, n):
    for j in range(n):
        for k in range(n):
            dp[i][j] = min(dp[i][j], c[j][k] + dp[i - 1][k])



ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] >= 0:
            ans += dp[n - 1][a[i][j]]

print(ans)

Solution (Python):
H,W = map(int,input().split())
c = [list(map(int,input().split())) for i in range(10)]
import queue



d = c.copy()
for k in range(10):
    for i in range(10):
        for j in range(10):
            if d[i][j] > d[i][k]+d[k][j]:
                d[i][j] = d[i][k]+d[k][j]

cost = []
for i in range(10):
    cost.append(d[i][1])

ans = 0
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        if A[j] != -1:
            ans += cost[A[j]]
print(ans)

Solution (Python):
H,W = map(int,input().split())
c = [list(map(int,input().split())) for i in range(10)]
import queue

def dist(i):
    res = c[i][1]
    que = queue.Queue()
    path = []
    for j in range(10):
        if j != i and j != 1:
            path.append(j)
    for j in range(10):
        if j != 1 and j != i and c[i][j] < res:
            jpath = path.copy()
            jpath.pop(jpath.index(j))
            que.put((j,c[i][j],jpath))
    while que.qsize():
        j,cost,path = que.get()
        if cost + c[j][1] < res:
            res = cost + c[j][1]
        for k in path:
            if k != 1 and cost+c[j][k] < res:
                kpath = path.copy()
                kpath.pop(kpath.index(k))
                que.put((k,cost+c[j][k],kpath))
    return res

cost = []
for i in range(10):
    cost.append(dist(i))

ans = 0
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        if A[j] != -1:
            ans += cost[A[j]]
print(ans)

Solution (Python):

c = []

def main():
    buf = input()
    buflist = buf.split()
    H = int(buflist[0])
    W = int(buflist[1])
    global c
    for i in range(10):
        buf = input()
        buflist = buf.split()
        c.append(list(map(int, buflist)))
    A = []
    for i in range(H):
        buf = input()
        buflist = buf.split()
        A.append(list(map(int, buflist)))
    cost_list = []
    for i in range(10):
        nlist = []
        for j in range(10):
            if j != 1:
                nlist.append(j)
        cost_list.append(min_cost_of(i, 1, 1, nlist, 0))
    number_count = []
    for i in range(10):
        i_count = 0
        for j in range(H):
            for k in range(W):
                if A[j][k] == i:
                    i_count += 1
        number_count.append(i_count)
    mp_needed = 0
    for i in range(10):
        mp_needed += cost_list[i] * number_count[i]
    print(mp_needed)

def min_cost_of(s, d, t, nlist, cost):
    if s == d or s == t:
        return cost
    else:
        minimum = c[s][d]
        for i in nlist:
            rlist = list(nlist)
            rlist.remove(i)
            result = min_cost_of(s, d, i, rlist, cost + c[i][t])
            if result < minimum:
                minimum = result
        return minimum

if __name__ == '__main__':
    main()