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: Runtime Error

Solution code:
import numpy as np
import itertools
_input = input
#'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

H, W = map(int, input().split(' '))
MPTable = np.array([list(map(int, input().split(' '))) for _ in range(10)])
NumTable = np.array([list(map(int, input().split(' '))) for _ in range(H)])
NumTable = NumTable.flatten()
NumTable2 = list(NumTable)
NumTable2.sort()
NumIter = itertools.groupby(NumTable2)
MPTo1 = MPTable[:,1]
def SearchLowest(i):
    next = {}
    for j, row in enumerate(MPTable):
        if MPTo1[j] > MPTo1[i]+row[i]:
            MPTo1[j] = MPTo1[i]+row[i]
            next[j] = MPTo1[j]
    if len(next.items()) == 0:
        return None
    else:
        min_val = min(next.values())
        keys = [key for key in next if next[key] == min_val]
        for k in keys:
            SearchLowest(k)
MPTo1[1] = 10000
m = np.argmin(MPTo1)
MPTo1[1] = 0
SearchLowest(m)
TotalMP = 0
for k, g in NumIter:
    if k != -1: TotalMP += MPTo1[k] * len(list(g))
print(TotalMP)
input = _input

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
C = [0]*10
for i in range(10):
    C[i] = list(map(int,input().split()))
A = [0]*10
for i in range(H):
    A[i] = list(map(int,input().split()))
for k in range(10):
    for i in range(10):
        for j in range(10):
            C[i][j] = min(C[i][j],C[i][k]+C[k][j])
Ans = 0
for i in range(H):
    B = A[i]
    for b in B:
        if b > 1:
            Ans += C[b][1]
print(Ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:

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

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

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


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

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

Submission status: Runtime Error

Solution code:

inp = raw_input().split("\r\n")
Size = inp[0]

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

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


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

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

Submission status: Runtime Error

Solution code:

inp = raw_input().split("\n")
Size = inp[0]

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

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


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

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

Submission status: Runtime Error

Solution code:
inp = raw_input().split("\n")
Size = inp[0]

Mml = [None, 0] + [None] * 8
Cij = []
for i in xrange(10):
    Cij.append(inp[i + 1].split(" "))

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


NumberList = [0] * 10
for Ai in inp[12:]:
    for A in Ai.split(" "):
        if A != -1:
            NumberList[A] += 1

ans = 0
for i, n in enumerate(NumberList):
    ans += sloveMm(i) * n
print ans

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
# This file was automatically generated by SWIG (http://www.swig.org).
# Version 3.0.8
#
# Do not make changes to this file unless you know what you are doing--modify
# the SWIG interface file instead.





from sys import version_info
if version_info >= (2, 6, 0):
    def swig_import_helper():
        from os.path import dirname
        import imp
        fp = None
        try:
            fp, pathname, description = imp.find_module('_ffi_c', [dirname(__file__)])
        except ImportError:
            import _ffi_c
            return _ffi_c
        if fp is not None:
            try:
                _mod = imp.load_module('_ffi_c', fp, pathname, description)
            finally:
                fp.close()
            return _mod
    _ffi_c = swig_import_helper()
    del swig_import_helper
else:
    import _ffi_c
del version_info
try:
    _swig_property = property
except NameError:
    pass  # Python < 2.2 doesn't have 'property'.


def _swig_setattr_nondynamic(self, class_type, name, value, static=1):
    if (name == "thisown"):
        return self.this.own(value)
    if (name == "this"):
        if type(value).__name__ == 'SwigPyObject':
            self.__dict__[name] = value
            return
    method = class_type.__swig_setmethods__.get(name, None)
    if method:
        return method(self, value)
    if (not static):
        if _newclass:
            object.__setattr__(self, name, value)
        else:
            self.__dict__[name] = value
    else:
        raise AttributeError("You cannot add attributes to %s" % self)


def _swig_setattr(self, class_type, name, value):
    return _swig_setattr_nondynamic(self, class_type, name, value, 0)


def _swig_getattr_nondynamic(self, class_type, name, static=1):
    if (name == "thisown"):
        return self.this.own()
    method = class_type.__swig_getmethods__.get(name, None)
    if method:
        return method(self)
    if (not static):
        return object.__getattr__(self, name)
    else:
        raise AttributeError(name)

def _swig_getattr(self, class_type, name):
    return _swig_getattr_nondynamic(self, class_type, name, 0)


def _swig_repr(self):
    try:
        strthis = "proxy of " + self.this.__repr__()
    except Exception:
        strthis = ""
    return "<%s.%s; %s >" % (self.__class__.__module__, self.__class__.__name__, strthis,)

try:
    _object = object
    _newclass = 1
except AttributeError:
    class _object:
        pass
    _newclass = 0



def init(h, w, c, a):
    return _ffi_c.init(h, w, c, a)
init = _ffi_c.init

def warshall_floyd(c):
    return _ffi_c.warshall_floyd(c)
warshall_floyd = _ffi_c.warshall_floyd

def ans(h, w, c, a):
    return _ffi_c.ans(h, w, c, a)
ans = _ffi_c.ans

def solve():
    return _ffi_c.solve()
solve = _ffi_c.solve

def main():
    return _ffi_c.main()
main = _ffi_c.main
# This file is compatible with both classic and new-style classes.


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

Submission status: Runtime Error

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: Runtime Error

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):
    ans += n[wl[a][b]]

print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
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 = [math.inf for _ in range(10)]
    distance[i] = 0
    not_reached = list(range(10))
    
    while (1 in not_reached):
        min_distance = math.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: Runtime Error

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 range(y):
            if a[j]!=-1:
                sum+=c[j][1]

    print(sum)

Submission status: Runtime Error

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 range(y):
            if a[j]!=-1:
                sum+=c[j][1]

    print(sum)

Submission status: Runtime Error

Solution code:
    def main():
        H,W = map(int,input().split())
     
        C = 10
        c = []
        for i in range(C):
            c.append(list(map(int,input().split())))
     
        a = []
        for i in range(H):
            a.append(list(map(int,input().split())))
     
        for k in range(C):
            for i in range(C):
                for j in range(C):
                    c[i][j] = min(c[i][j],c[i][k]+c[k][j])
     
        ans = 0
        for i in range(H):
            for j in range(W):
                if a[i][j] != -1:
                    ans += c[a[i][j]][1]
        print(ans)
     
    if __name__ == '__main__':
        main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
    from scipy.sparse.csgraph import dijkstra
     
    H, W = map(int,input().split())
    c = [[0 for i in range(10)] for j in range(10)]
    for i in range(10):
        c[i] = list(map(int, input().split()))
    t = dijkstra(c)
    ans = 0
    for i in range(H):
        for k in map(int, input().split()):
            if k == 1 or k == -1: continue
            ans += t[k][1]
    print(int(ans))

Submission status: Runtime Error

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])
print(sum([sum(map(lambda a: 0 if a == -1 else C[a][1], row)) for row in A])

Submission status: Runtime Error

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(4):
    for i in range(10):
        for j in range(10):
            C[i][j] = min(C[i][j], C[i][k] + C[k][j])
print(sum([sum(map(lambda a: 0 if a == -1 else C[a][1], row)) for row in A])

Submission status: Runtime Error

Solution code:
def dijkstra(graph,src):
    if graph is None:
        return None
    nodes = [i for i in range(len(graph))]
    visited=[]
    if src in nodes:
        visited.append(src)
        nodes.remove(src)
    else:
        return None
    distance={src:0}
    for i in nodes:
        distance[i]=int(graph[src][i])
    path={src:{src:[]}}
    k=pre=src
    while nodes:
        mid_distance=float('inf')
        for v in visited:
            for d in nodes:
                new_distance = int(graph[src][v])+int(graph[v][d])
                if new_distance < mid_distance:
                    mid_distance=new_distance
                    graph[src][d]=str(new_distance)
                    k=d
                    pre=v
        distance[k]=mid_distance
        path[src][k]=[i for i in path[src][pre]]
        path[src][k].append(k)
        visited.append(k)
        nodes.remove(k)
    return distance

if __name__=="__main__":
    sum = 0
    s = input().split(" ")
    x, y = s[0], s[1]
    c = [n for n in range(0,10)]
    d = {}*10
    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[m] = 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[j][1])
    print(sum)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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

    return dist

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

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

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

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

print(res)

Submission status: Runtime Error

Solution code:
h,w=[int(i) for i in input().split(" ")]
m=[[0 for i in range(10)]for i in range(10)]
for i in range(10):
  m[i]=[int(i) for i in input().split(" ")]

def rmin(b,yt,ys,m):
  if i in range(10):
    if yt + m[b][i] + m[i][1] < ys:
       ys =yt + m[b][i] + m[i][1]
    if yt + m[b][i] < ys:
       ys =rmin(i , yt + m[b][i] ,ys,m)
  return ys
x=0
for i in range(h):
  b0 = [int(i) for i in input().split(" ")]

  for j in b0:
    if j ==1 or j==-1:
      x=x
    else:
      b=j
      
      x+=rmin(b,0,m[b][1],m)
print(x)

Submission status: Runtime Error

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

#thanks lethe2211!!
class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        num = len(adj)          # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
        
        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

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

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

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

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

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

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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

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

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

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

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

print(res)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop

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


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

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

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


dist = dijkstra(G, 8)
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)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))


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

print(ans)

Submission status: Runtime Error

Solution code:
fantastic!!

Submission status: Runtime Error

Solution code:
input!!!!
good!