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:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    h,w = LI()
    t = [LI() for _ in range(10)]
    a = [LI() for _ in range(h)]
    e = collections.defaultdict(list)
    for i in range(10):
        for j in range(10):
            e[i].append((j,t[j][i]))

    def search(s):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    d = search(1)
    r = 0
    for b in a:
        for c in b:
            if c*c == 1:
                continue
            r += d[c]

    return r



print(main())

Submission status: Accepted

Solution code:
def WF(lenV,E):
	D = E
	r = range(lenV)
	for k in r:
		for i in r:
			for j in r:
				D[i][j] = min(D[i][j], D[i][k]+D[k][j])
	return D
				
IN = input().split()
H = int(IN[0])
W = int(IN[1])
R = range(10)
E = [[float("inf") for i in R] for j in R]
for i in R:
	IN = input().split()
	for j in R:
		E[i][j] = int(IN[j])
D = WF(10,E)
C = [D[i][1] for i in R]
Ans = 0
for h in range(H):
	IN = input().split()
	for w in range(W):
		wall = int(IN[w])
		Ans += C[wall] if wall>=0 else 0
print(Ans)

Submission status: Accepted

Solution code:
import heapq


def func(start, mp):
    d = [float("inf") for i in xrange(10)]
    d[start] = 0
    q = [(0, start)]
    while len(q):
        c, n = heapq.heappop(q)
        if d[n] < c:
            continue
        for i in xrange(10):
            if d[i] > d[n]+mp[n][i]:
                d[i] = d[n]+mp[n][i]
                heapq.heappush(q, (d[i], i))
    return d[1]

h, w = map(int, raw_input().split())
mp = list()
for i in xrange(10):
    mp.append(map(int, raw_input().split()))

m = [func(i, mp) for i in xrange(10)]
print sum([sum(map(lambda x:m[x] if not x == -1 else 0, map(int, raw_input().split()))) for i in xrange(h)])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter
from heapq import heappush, heappop

def inpl(): return map(int, input().split())
H, W = inpl()
C = []
A = Counter()

for _ in range(10):
    C.append(tuple(inpl()))

for _ in range(H):
    A.update(tuple(inpl()))

min_cost = [float("inf") for _ in range(10)]
# ダイクストラ
g = 1
for s in range(10):
    searched = [False] * 10
    searched[s] = True
    N = 10
    INF = float("inf")
    d = [INF for _ in range(N)]
    d[s] = 0
    heap = [[0, s]] # cost, destination
    
    while len(heap):
        pcost, p = heappop(heap)
        searched[p] = True
        
        if d[p] < pcost:
            continue
        
        for i in range(10):
            if not searched[i]:
                new_cost = pcost + C[p][i]
                if new_cost < d[i]:
                    d[i] = new_cost
                    heappush(heap, [new_cost, i])
        
    min_cost[s] = d[1]

res = 0
for i in range(10):
    res += A[i] * min_cost[i]

print(res)

Submission status: Accepted

Solution code:
def cost(n,clist):
  for k in range(0,10):
    for i in range(0,10):
      for j in range(0,10):
        clist[i][j] = min(clist[i][j],clist[i][k]+clist[k][j])
  
  return clist[n][1]

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

if __name__ == '__main__':
  h,w,clist,a = i_o()
  ans =joisino(a,clist)
  
  print(ans, flush=True)

Submission status: Accepted

Solution code:
def cost(n,clist):
  k = 0
  while k < 10:
    i = 0
    while i < 10:
      j = 0
      while j < 10:
        clist[i][j] = min(clist[i][j],clist[i][k]+clist[k][j])
        j += 1
      i += 1
    k += 1
  return clist[n][1]

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

if __name__ == '__main__':
  h,w,clist,a = i_o()
  ans =joisino(a,clist)
  
  print(ans, flush=True)

Submission status: Accepted

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

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

for i in range(H):
	for j in range(W):
		if wall[i][j] != 1 and wall[i][j] != -1:
			cost += m[wall[i][j]][1]

print(cost)

Submission status: Accepted

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

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

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 = sum([c[a][1] for a in itertools.chain.from_iterable(A) if a >= 0])
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) ]
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] >= 0:
      ans += c[A[i][j]][1]
print(ans)

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
h,w = map(int, raw_input().split(" "))
c = []
for i in range(10):
    c.append(map(int, raw_input().split(" ")))

'''
def change(number):
    if number == -1:
        return 10
'''


a = []
for i in range(h):
    a.append(map(int, raw_input().split(" ")))

route = range(10)

def minroute(nowplace,d,passway,k):
    passp = passway[:]
    passp.append(nowplace)
    d1 = d + c[nowplace][1]
    for i in range(10):
        if (i in passp) or (c[nowplace][1] <= c[nowplace][i]): continue
        else:
            dk = minroute(i,d+c[nowplace][i],passp,k)
            if d1 > dk:
                d1 = dk
    return d1


for i in range(10):
    if i == 1:
        route[1] = 0
        continue
    route[i] = minroute(i,0,[1],i)

mp = 0
for l in a:
    for i in l:
        if i == -1:
            mp += 0
        else:
            mp += route[i]

print mp

Submission status: Accepted

Solution code:
def solve():
    H, W = list(map(int, input().split(" ")))
    d, A = [], []
    for _ in range(10):
        d.append(list(map(int, input().split(" "))))
    for _ in range(H):
        A += list(map(int, input().split(" ")))

    V, E = 10, 35
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

    sum = 0
    for a in A:
        if a == -1:
            pass
        else:
            sum += d[a][1]

    print(sum)
 

solve()

Submission status: Accepted

Solution code:
# coding: utf-8
h,w=map(int,input().split())
cost=[]
for i in range(10):
    cost.append(list(map(int,input().split())))

for i in range(10):
    for j in range(10):
        for k in range(10):
            if cost[j][k]>cost[j][i]+cost[i][k]:
                cost[j][k]=cost[j][i]+cost[i][k]
ans=0
for i in range(h):
    for j in map(int,input().split()):
        if j!=-1:
            ans+=cost[j][1]
print(ans)

Submission status: Accepted

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

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

wall = [list(map(int, input().split())) for i in range(H) ]
ans = 0

for h in range(H):
  for w in range(W):
    if wall[h][w] < 0:
      continue
    ans += A[wall[h][w]][1]

print(ans)

Submission status: Accepted

Solution code:
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

if __name__ == '__main__':
  h,w,clist,a = i_o()
  ans =joisino(a,clist)
  
  print(ans, flush=True)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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):
 # print("invoked")
  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)

Submission status: Accepted

Solution code:
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)

# 4近傍（右, 下, 左, 上）
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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

Submission status: Accepted

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

import numpy as np

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

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

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

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

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

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

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

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

print ans

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
C = []
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

cost_matrix = [] ##adjacency 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)

##Floyd-Warshall
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# coding: utf-8

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)

Submission status: Accepted

Solution code:
# coding: utf-8

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
# print sum(sum(d[a] if a != -1 else 0 for a in aa) for aa in A)

Submission status: Accepted

Solution code:
    # coding: utf-8
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

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


h,w = IL()
G = [[] for i in range(10)]
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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)