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):
def rec_cost(x,acc,plist,clist):
  if x == 1:
    return acc
  else:
    minimum = -1
    for next in plist:
      nextplist = plist.copy()
      nextplist.remove(next)
      candidate = rec_cost(next,acc+clist[x][next],nextplist,clist)
      if minimum == -1:
        minimum = candidate
      elif candidate < minimum:
        minimum = candidate
    return minimum
      

def cost(n,clist):
  plist = [0,1,2,3,4,5,6,7,8,9]
  plist.remove(n)
  return rec_cost(n,0,plist,clist)

def joisino(a,clist):
  note = [-1,0,-1,-1,-1,-1,-1,-1,-1,-1]
  answer = 0
  for raw in a:
    for number in raw:
      if number != -1:
        if note[number] == -1:
          note[number] = cost(number,clist)
        answer += note[number]
      
  return answer

def i_o():
  h, w = map(int,input().split(" "))
  i = 0 
  clist = []
  while i < 10:
    raw = list(map(int,input().split(" ")))
    clist.append(raw)
    i += 1
  a = []
  i = 1
  while i <= h:
    raw = list(map(int,input().split(" ")))
    a.append(raw)
    i += 1
  return h,w,clist,a

def fact(n):
  if n == 1:
    return 1
  else:
    return n * fact(n-1)
  
  
 
if __name__ == '__main__':
  h,w,clist,a = i_o()
  ans =joisino(a,clist)
  
  print(ans, flush=True)

Solution (Python):
def solve(inputstr):
  return inputstr

def rec_cost(x,acc,plist,clist):
  if x == 1:
    return acc
  else:
    minimum = -1
    for next in plist:
      nextplist = plist.copy()
      nextplist.remove(next)
      candidate = rec_cost(next,acc+clist[x][next],nextplist,clist)
      if minimum == -1:
        minimum = candidate
      elif candidate < minimum:
        minimum = candidate
    return minimum
      

def cost(n,clist):
 
  plist = [0,1,2,3,4,5,6,7,8,9]
  plist.remove(n)
  return rec_cost(n,0,plist,clist)

def joisino(a,clist):
  note = [-1,0,-1,-1,-1,-1,-1,-1,-1,-1]
  answer = 0
  for raw in a:
    for number in raw:
      if number != -1:
        if note[number] == -1:
          note[number] = cost(number,clist)
        answer += note[number]
      
  return answer

def i_o():
  h, w = map(int,input().split(" "))
  i = 0 
  clist = []
  while i < 10:
    raw = list(map(int,input().split(" ")))
    clist.append(raw)
    i += 1
  a = []
  i = 1
  while i <= h:
    raw = list(map(int,input().split(" ")))
    a.append(raw)
    i += 1
  return h,w,clist,a

def fact(n):
  if n == 1:
    return 1
  else:
    return n * fact(n-1)
  
  
 
if __name__ == '__main__':
  h,w,clist,a = i_o()
  ans =joisino(a,clist)
  
  print(ans, flush=True)

Solution (Python):
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
INF = float("inf")
sys.setrecursionlimit(10**7)


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


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

    dp = [[0] * 10 for _ in range(10)]
    for i in range(10):
        line = input().split()
        for j, c in enumerate(line):
            dp[i][j] = int(c)

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

    for m in range(10):
        for s in range(10):
            for e in range(10):
                if dp[s][m] != INF and dp[m][e] != INF:
                    dist = dp[s][m] + dp[m][e]
                    if dist < dp[s][e]:
                        dp[s][e] = dist
    ans = 0
    for _ in range(H):
        line = input().split()
        for x in range(W):
            n = int(line[x])
            if n != -1:
                ans += dp[n][1]
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
h, w = [int(i) for i in input().split()]
k = []
wl = []
  
for i in range(0, 10):
  k.append([int(i) for i in input().split()])
for i in range(0, h):
  wl.append([int(i) for i in input().split()])
 
 
n = {1:0}
 
while len(n) < 10:
  c = 1000
  mn = 10
  for a in n.keys():
    a2 = int(a)
    for b in range(0, 10):
      if not b in n:
        if k[b][a2] + n[a] <= c:
          c = k[b][a2] + n[a]
          mn = b
  n[mn] = c
 
ans = 0
for a in range(0, h):
  for b in range(0, w):
    if wl[a][b] != -1:
      ans += n[wl[a][b]]
 
print(ans)

Solution (Python):


import heapq

INF = float("inf")

def dijkstra(graph, st):
    n  = len(graph)
    ds = [INF]*n
    ds[st] = 0
    prevs = [None]*n
    
    qs = [(0, st)]

    while len(qs) > 0:
        d, nodeId = heapq.heappop(qs)
        
        if d > ds[nodeId]:
            continue
        
        for destId, length in graph[nodeId]:
            d2 = d + length
            if ds[destId] > d2:
                ds[destId] = d2
                prevs[destId] = nodeId
                heapq.heappush(qs, (d2, destId))
                
    return (ds, prevs)


def f(H, W, C, A):
    graph = [[(i, C[i][j]) for i in range(10)] for j in range(10)]
    ds, _ = dijkstra(graph, 1)

    return sum(ds[a] if a>= 0 else 0 for line in A for a in line)

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

    print(f(H,W,C,A))


if __name__ == '__main__':
    main()

Solution (Python):
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):
            if c[i][k] + c[k][j] < c[i][j]:
                c[i][j] = c[i][k] + c[k][j]

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

Solution (Python):



"""abc079_d"""

import sys
import pprint
import re

import itertools
pp = pprint.PrettyPrinter(indent=2)


def main():
    """Main function."""
    h,w = list(map(int, input().split(' ')))

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

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

    for k in range(10):
        for i in range(10):
            for j in range(10):
                if cs[i][j] > cs[i][k] + cs[k][j]:
                    cs[i][j] = cs[i][k] + cs[k][j]

    res = 0
    for line in as_:
        for v in line:
            if v != -1:
                res += cs[v][1]

    print(res)


if __name__ == '__main__':
    sys.exit(main())

Solution (Python):



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)







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)-1:
    
    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

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

for i in range(10):
    for n in range(10):
        for m in range(10):
            C[n][m] = min(C[n][m], C[n][i] + C[i][m])

for a in range(H):
    for b in range(W):
        if A[a][b] != -1:
            ans += C[A[a][b]][1]

print(ans)

Solution (Python):
import itertools 

def wall(A,c,H,W):
    for k in range(10):
        for i,j in itertools.product(range(10), range(10)):
            c[i][j] = min(c[i][j], c[i][k]+c[k][j])

    cost = 0
    for i,j in itertools.product(range(H), range(W)):
        if A[i][j] != -1 and A[i][j] != 1:
            cost += c[A[i][j]][1]
    print(cost)


items = list(map(int, input().split()))
H = items[0]
W = items[1]
c = list()
A = list()
for i in range(10):
	c_i = list(map(int, input().split()))
	c.append(c_i)
for i in range(H):
	A_i = list(map(int, input().split()))
	A.append(A_i)
wall(A,c,H,W)

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

cost_matrix = [] 
for i in range(10):
    cost_matrix.append([int(x) for x in input().split()])

freq = [0 for x in range(10)]
for i in range(H):
    row = [int(x) for x in input().split()]
    for i in range(10):
        freq[i] += row.count(i)


for k in range(10):
    for i in range(10):
        for j in range(10):
            if cost_matrix[i][k] == -1 or cost_matrix[k][j] == -1:
                continue
            if cost_matrix[i][j] == -1 or cost_matrix[i][j] > cost_matrix[i][k] + cost_matrix[k][j]:
                cost_matrix[i][j] = cost_matrix[i][k] + cost_matrix[k][j]

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

Solution (Python):
def main():
    H, W = map(int, input().split())
    C = tuple(tuple(map(int, input().split())) for _ in [0] * 10)
    A = ' '.join([input() for _ in [0] * H])

    a = []
    apnd = a.append
    for s in A.split():
        if s != '-1' and s != '1':
            apnd(int(s))

    dist = []
    apnd = dist.append
    for n in C:
        apnd(list(n))

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

    ans = 0
    for i in a:
        ans += dist[i][1]
    print(ans)

main()

Solution (Python):
def Warshall_Floyd(edges,N):
  import copy
  d=copy.deepcopy(edges)
  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])
  return d

H,W=map(int,input().split())
path1=[list(map(int,input().split())) for i in range(10)]
Path=Warshall_Floyd(path1,10)
ans=0
for i in range(H):
  w=list(map(int,input().split()))
  for j in range(W):
    if w[j]==-1: continue
    ans+=Path[w[j]][1]
print(ans)

Solution (Python):


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

c = [map(int, raw_input().split()) for _ in xrange(10)]
A = [map(int, raw_input().split()) for _ in xrange(H)]
d = [float('inf')] * 10

d[1] = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            if d[j] != float('inf') and d[k] > d[j] + c[k][j]:
                d[k] = d[j] + c[k][j]

print sum(sum(d[a] if a != -1 else 0 for a in aa) for aa in A)

Solution (Python):


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

c = [map(int, raw_input().split()) for _ in xrange(10)]
A = [map(int, raw_input().split()) for _ in xrange(H)]
d = [float('inf')] * 10

def bellman_ford(s):
    d[s] = 0
    for i in range(10):
        for j in range(10):
            for k in range(10):
                if d[j] != float('inf') and d[k] > d[j] + c[k][j]:
                    d[k] = d[j] + c[k][j]

bellman_ford(1)
ans = 0

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

print ans

Solution (Python):
    
H, W = (int(x) for x in input().split())
 
convert = [[int(x) for x in input().split()] for _ in range(10)]
table = [[int(x) for x in input().split()] for _ in range(H)]
 
conv_to_one = [0] * 10
for i in [x for x in range(10) if (x != 1)]:
    distance = [float("inf") for _ in range(10)]
    distance[i] = 0
    not_reached = list(range(10))
    
    while (1 in not_reached):
        min_distance = float("inf")
        new_reached = None
        for num in not_reached:
            if (distance[num] < min_distance):
                min_distance = distance[num]
                new_reached = num
        not_reached.remove(new_reached)
 
        for num in not_reached:
            if min_distance + convert[new_reached][num] < distance[num]:
                distance[num] = min_distance + convert[new_reached][num]
    conv_to_one[i] = distance[1]
 
count = [0] * 10
for row in table:
    for elem in row:
        if elem != -1:
            count[elem] += 1
 
 
result = sum([cnt * cnv for cnt,cnv in zip(count, conv_to_one)])
print(result)

Solution (Python):
if __name__=="__main__":
    sum = 0
    x,y = map(int,input().split())
    c = [list(map(int,input().split())) for n in range(10)]
    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]

    for i in range(x):
        a = list(map(int,input().split()))
        for j in a:
            if j!=-1:
                sum+=c[j][1]

    print(sum)

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

if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin
import math
import bisect
from collections import defaultdict

def IL():return list(map(int, stdin.readline().split()))
def ItoSList(): return list(map(int,list(stdin.readline())))
def IL_reverse():return list(map(int, stdin.readline().split())).reverse()
def Int_all():return list(map(int, stdin))
def sumIL():return sum(list(map(int, stdin.readline().split())))
def SL():return list(map(int, stdin.readline().split()))
def Str_all():return list(map(int, stdin))
def tDL(p,q):return [[0 for i in range(p)] for j in range(q)]


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

N=10
res = float('inf')
dist = [[float("inf")] * N for i in range(N)]
def main():
	H,W = IL()
	for i in range(N):
		dist[i][i] = 0
	
	G = [[] for i in range(N)]
 
	for i in range(10):
	    l = IL()
	    for j in range(10):
	        dist[i][j] = l[j]
	floyd_warshall()

	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 = dist[i][1] 
	            memo[i] = t
	            ans += t
	print(ans)

if __name__ == "__main__": main()

Solution (Python):
if __name__=="__main__":
    sum = 0
    x,y = map(int,input().split())
    c = [list(map(int,input().split())) for n in range(10)]
    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]

    m = [list(map(int,input().split())) for n in range(int(x))]
    for i in range(x):
        for j in range(y):
            if m[i][j]!=-1:
                sum+=int(c[m[i][j]][1])

    print(sum)

Solution (Python):
h, w = map(int, input().split())
mp = []
for i in range(10):
    mp.append(list(map(int, input().split())))
wall = []
for i in range(h):
    wall.append(list(map(int, input().split())))

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

ans = 0
for i in range(h):
    for n in wall[i]:
        if n != -1 and n != 1:
            ans += min_mp[n][1]

print(ans)

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

Solution (Python):
h, w = map(int, input().split())
mp = []
for i in range(10):
    mp.append(list(map(int, input().split())))
wall = []
for i in range(h):
    wall.append(list(map(int, input().split())))

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

ans = 0
for i in range(h):
    for n in wall[i]:
        if n != -1 and n != 1:
            ans += min_mp[n][1]

print(ans)

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

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

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

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] 
        >>> 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] 
        '''
        num = len(adj)          
        dist = [float('inf') for i in range(num)] 
        prev = [float('inf') for i in range(num)] 
        
        dist[start] = 0
        q = []                  
        heapq.heappush(q, (0, start)) 

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) 
            
            
            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 
                    heapq.heappush(q, (dist[dest], dest)) 
                    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]

        
        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)

Solution (Python):




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

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

Solution (Python):
def d_wall(H, W, C, A):
    
    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]  
    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))

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

Solution (Python):

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



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



def djk(n):
	
	Start=n

	
	d=[-1 for i in range(10)]
	d[Start]=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
			
			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

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

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