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: Wrong Answer

Solution code:
import numpy as np
import itertools

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)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

def dfs(n,sum,val):
    # 1に辿り着いたらsumをcostへ登録
    if n == 1:
        costMemo[val] = min(sum,costMemo[val])
        return
    # sumが現在の最小より大きい場合return
    if sum > costMemo[val]:
        return
    # 直接1に行く場合
    dfs(1,sum + c[n][1],val)
    # 配列内に1に行くより低いコストがある場合
    a = [i for i, j in enumerate(c[n]) if 0 < c[n][i] < c[n][1]]
    for i in range(len(a)):
        dfs(a[i],sum + c[n][a[i]],val)

# costMemo製作
for i in range(10):
    dfs(i,0,i)

ans = 0
# Aから-1,1以外を低コストで変換する
for i in range(H):
    for j in range(W):
        if A[i][j] >= 0:
            ans += costMemo[A[i][j]]

print(ans)

Submission status: Wrong Answer

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

def dfs(n,sum,val):
    # 1に辿り着いたらsumをcostへ登録
    if n == 1:
        costMemo[val] = min(sum,costMemo[val])
        return
    # sumが現在の最小より大きい場合return
    if sum > costMemo[val]:
        return
    # 直接1に行く場合
    dfs(1,sum + c[n][1],val)
    # 配列内に1に行くより低いコストがある場合
    a = [i for i, j in enumerate(c[n]) if 0 < c[n][i] < c[n][1]]
    for i in range(len(a)):
        dfs(a[i],sum + c[n][a[i]],val)

# costMemo製作
for i in range(10):
    dfs(i,0,i)

ans = 0
# Aから-1,1以外を低コストで変換する
for i in range(H):
    for j in range(W):
        if A[i][j] > 1 or A[i][j] == 0:
            ans += costMemo[A[i][j]]

print(ans)

Submission status: Wrong Answer

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

def dfs(n,sum,val):
    # sumが現在の最小より大きい場合return
    if sum > costMemo[val]:
        return
    # 1に辿り着いたらsumをcostへ登録
    if n == 1:
        costMemo[val] = min(sum,costMemo[val])
        return
    # 直接1に行く場合
    dfs(1,sum + c[n][1],val)
    # 配列内に1に行くより低いコストがある場合
    a = [i for i, j in enumerate(c[n]) if 0 < c[n][i] < c[n][1]]
    for i in range(len(a)):
        dfs(a[i],sum + c[n][a[i]],val)

# costMemo製作
for i in range(10):
    dfs(i,0,i)

ans = 0
# Aから-1,1以外を低コストで変換する
for i in range(H):
    for j in range(W):
        if A[i][j] > 1 or A[i][j] == 0:
            ans += costMemo[A[i][j]]

print(ans)

Submission status: Wrong Answer

Solution code:
H, W = list(map(int, input().split()))
c, A = [], []

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

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

t = [[1000 for i in range(10)] for j in range(10)]

count = 0
x = 0

while count < 100:
    next = 1000

    for j in range(10):
        for i in range(10):
            if c[j][i] == x:

                min_mp = 10000
                for y in range(10):
                    min_mp = min(t[j][y] + t[y][i], min_mp)
                t[j][i] = min(c[j][i], min_mp)
                count += 1

            elif c[j][i] < next and c[j][i] > x:
                next = c[j][i]
    x = next

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

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import collections
h,w = (int(i) for i in input().split())
c = [[int(i) for i in input().split()] for i in range(10)]
a = [[int(i) for i in input().split()] for i in range(h)]
for i in range(10):
		for j in range(10):
			for k in range(10):
				c[i][j] = min(c[i][k]+c[k][j],c[i][j])
x,answer = [],0
for i in a: x+=i
y = collections.Counter(x)
for i in range(10):
	answer += y[i]*c[i][1]
print(answer)

Submission status: Wrong Answer

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

front = 0
last = 0

queue = [[0, 0, [True for j in range(10)]] for i in range(10000)]

def push(num):
    global last
    global queue
    queue[last] = num
    last = (last + 1)%10000

def pop():
    global front
    global queue
    num = queue[front]
    front = (front + 1)%10000
    return num

def len():
    global last
    global front
    length = last - front
    return length + 10000 if (length < 0) else length

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

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

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

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

def bfs(num):
    global G
    global lenList
    x = [num[0], num[1], [num[2][i] for i in range(10)]]
    
    #行ったことあるフラグの更新
    x[2][x[0]] = False

    #進んできた距離が最短より短ければ更新
    if x[1] < lenList[x[0]]:
        lenList[x[0]] = x[1]

    #行ったことないならプッシュ
    for i in range(10):
        if x[2][i]:
            push([i, x[1]+G[i][x[0]], x[2]])

#初期値を入力して発火
push([1, 0, [True for i in range(10)]])
while len() != 0:
    bfs(pop())

sum = 0

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

print(sum)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
INF = 100000

front = 0
last = 0

queue = [[0, 0, [True for j in range(10)]] for i in range(10000)]

def push(num):
    global last
    global queue
    queue[last] = num
    last = (last + 1)%10000

def pop():
    global front
    global queue
    num = queue[front]
    front = (front + 1)%10000
    return num

def len():
    global last
    global front
    length = last - front
    return length + 10000 if (length < 0) else length

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

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

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

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

def bfs(num):
    global G
    global lenList
    x = [num[0], num[1], [num[2][i] for i in range(10)]]
    
    #行ったことあるフラグの更新
    x[2][x[0]] = False

    #進んできた距離が最短より短ければ更新
    if x[1] < lenList[x[0]]:
        lenList[x[0]] = x[1]

    #行ったことないならプッシュ
    for i in range(10):
        if x[2][i]:
            push([i, x[1]+G[i][x[0]], x[2]])

#初期値を入力して発火
push([1, 0, [True for i in range(10)]])
while len() != 0:
    bfs(pop())

sum = 0

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

print(sum)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
INF = 100000

front = 0
last = 0
gcounter = 0

queue = [[0, 0, [True for j in range(10)]] for i in range(10000)]

def push(num):
    global last
    global queue
    queue[last] = num
    last = (last + 1)%10000

def pop():
    global front
    global queue
    num = queue[front]
    front = (front + 1)%10000
    return num

def len():
    global last
    global front
    length = last - front
    return length + 10000 if (length < 0) else length

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

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

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

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

def bfs(num):
    global gcounter
    global G
    global lenList
    x = [num[0], num[1], [num[2][i] for i in range(10)]]
    gcounter += 1
    #行ったことあるフラグの更新
    x[2][x[0]] = False

    #進んできた距離が最短より短ければ更新
    if x[1] < lenList[x[0]]:
        lenList[x[0]] = x[1]

    #行ったことないならプッシュ
    for i in range(10):
        if x[2][i]:
            y = [i, x[1]+G[i][x[0]], x[2]]
            push(y)

#初期値を入力して発火
push([1, 0, [True for i in range(10)]])
while len() != 0:
    bfs(pop())

sum = 0

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

print(sum)

Submission status: Wrong Answer

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

for i in range(10):
    for j in range(10):
        for k in range(10):
            c[i][j] = min((c[i][j], c[i][k] + c[k][j]))
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == -1:
            continue
        ans += c[A[i][j]][1]
print(ans)

Submission status: Wrong Answer

Solution code:
H, W=map(int,input().split())
c=[list(map(int,input().split())) for _ in range(10)]
a=[list(map(int,input().split())) for _ in range(H)]
ans=0

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

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

print(ans)

Submission status: Wrong Answer

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
H, W=map(int,input().split(' '))
c=[list(map(int,input().split(' '))) for i in range(10)]
a=[list(map(int,input().split(' '))) for i in range(H)]
ans=0

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
H, W=map(int,input().split(' '))
c=[list(map(int,input().split(' '))) for i in range(10)]
a=[list(map(int,input().split(' '))) for i in range(H)]
ans=0

for i in range(10):
    for j in range(10):
        for k 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(H):
    for j in range(W):
        if a[i][j]>=0:
            ans += c[a[i][j]][1]

print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, raw_input().split())
c = [map(int, raw_input().split()) for _ in range(10)]
A = [map(int, raw_input().split()) for _ in range(H)]

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

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

Submission status: Wrong Answer

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

for k in range(10):
    for i in range(10):
        for j in range(10):
            c1 = c[i][j]
            c2 = c[i][k] + c[k][j]
            if c2 > c1:
                c[i][j] = c2
ans = 0
for _ in range(H):
    for a in map(int, input().split()):
        if a != -1:
            ans += c[a][1]

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np


def dijkstra(N, matrix, s):
    d = [np.inf for _ in range(N)]
    d[s] = 0
    Q = set([i for i in range(N)])

    def min_index():
        mi = np.inf
        mii = 0
        for i in Q:
            if d[i] < mi:
                mii = i
        return mii

    while Q:
        u = min_index()
        Q.remove(u)
        for v in range(N):
            if matrix[u][v] > 0:
                alt = d[u] + matrix[u][v]
                if d[v] > alt:
                    d[v] = alt
    return d


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

c = []

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

c = list(map(list, zip(*c)))

k = [0 for _ in range(10)]

for _ in range(H):
    xs = [int(x) for x in input().split()]
    for x in xs:
        if x > 0:
            k[x] += 1

d = dijkstra(10, c, 1)

count = sum([d[i] * k[i] for i in range(10)])

print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
from copy import deepcopy


def dijkstra(N, matrix, s):
    d = [np.inf for _ in range(N)]
    d[s] = 0
    prev = [-1 for _ in range(N)]
    Q = set([i for i in range(N)])

    def min_index():
        mi = np.inf
        mii = 0
        for i in Q:
            if d[i] < mi:
                mii = i
        return mii

    while Q:
        u = min_index()
        Q.remove(u)
        for v in range(N):
            if matrix[u][v] >= 0:
                alt = d[u] + matrix[u][v]
                if d[v] > alt:
                    d[v] = alt
                    prev[v] = u
    return d


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

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

c_tmp = deepcopy(c)

for i in range(10):
    for j in range(10):
        c_tmp[i][j] = c[j][i]

c = c_tmp

k = [0 for _ in range(10)]
for i in range(H):
    xs = [int(x) for x in input().split()]
    for x in xs:
        if x > 0:
            k[x] += 1

d = dijkstra(10, c, 1)

count = 0
for i in range(10):
    if i != 1:
        count += d[i] * k[i]

print(count)

Submission status: Wrong Answer

Solution code:
str = """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
"""

inp = str.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: Wrong Answer

Solution code:
str = """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
"""

inp = str.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: Wrong Answer

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

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


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


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

    warshallFloyd(10, dp)

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


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

Submission status: Wrong Answer

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: Wrong Answer

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 list(itertools.chain.from_iterable(A)) if a > 0])
print(ans)

Submission status: Wrong Answer

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: Wrong Answer

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

for i in range(10):
  for j in range(10):
    for k in range(10):
      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: Wrong Answer

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 = [0,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: Wrong Answer

Solution code:
h, w = map(int, input().split(" "))

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

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: Wrong Answer

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 i in range(10):
        for j in range(10):
            for k 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: Wrong Answer

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):
            if C[i][n] > C[i][m] + C[m][n]:
                C[i][n] = C[i][m] + C[m][n]

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

print(ans)

Submission status: Wrong Answer

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())))
check = []

for i in range(10):
    for n in range(10):
        for m in range(10):
            if C[i][n] > C[i][m] + C[m][n]:
                C[i][n] = C[i][m] + C[m][n]

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: Wrong Answer

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

min_val = -1


def search(n, current, searched):
    global min_val
    for idx, val in enumerate(C[n]):
        if val + current < min_val and idx not in searched:
            if idx == 1:
                if val + current < min_val:
                    min_val = val + current
                    return
            else:
                new_searched = searched[:]
                new_searched.append(idx)
                search(idx, val + current, new_searched)

min_vals = []
for i in range(10):
    min_val = C[i][1]
    search(i, 0, [i])
    min_vals.append(min_val)

ans = 0
for Ai in A:
    for Aij in Ai:
        if Aij != -1:
            ans += min_vals[Aij]
print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
c = []
minu = []
indexnumber = []
for i in range(10):
	d = list(map(int,input().split()))
	c.append(d)
	minsec = max(d)
	for e in range(10):
		if d[e] < minsec and d[e] != 0:
			minsec = d[e]
	minu.append(minsec)
	indexnumber.append(d.index(minu[i]))
#c[1][2]は上から二段目よこから三行目

a = []
youso = [0,0,0,0,0,0,0,0,0,0]
for i in range(h):
	k = list(map(int,input().split()))
	a.append(k)
	for s in range(10):
		youso[s] += k.count(s) #あってるらしい

#i→1のとき
mplist = []
for i in range(0,10):
	y = i
	mp = 0
	if y == 1:
		mplist.append(0)
	else:
		while y != 1 and mp <= c[i][1] + 1000:
			mp = mp + minu[i]
			y = indexnumber[y]
		if mp <= c[i][1]:
			mplist.append(mp)
		elif mp > c[i][1]:
			mplist.append(c[i][1])

totalmp = 0
for i in range(10):
	totalmp += mplist[i]*youso[i]

print(totalmp)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
c = []
minu = []
indexnumber = []
for i in range(10):
	d = list(map(int,input().split()))
	c.append(d)
	minsec = max(d)
	for e in range(10):
		if d[e] < minsec and d[e] != 0:
			minsec = d[e]
	minu.append(minsec)
	indexnumber.append(d.index(minu[i]))
#c[1][2]は上から二段目よこから三行目

a = []
youso = [0,0,0,0,0,0,0,0,0,0]
for i in range(h):
	k = list(map(int,input().split()))
	a.append(k)
	for s in range(10):
		youso[s] += k.count(s) #あってるらしい

#i→1のとき
mplist = []
for i in range(0,10):
	y = i
	mp = 0
	if y == 1:
		mplist.append(0)
	else:
		while y != 1 and mp <= c[i][1] + 1000:
			mp = mp + minu[i]
			y = indexnumber[y]
		if mp <= c[i][1]:
			mplist.append(mp)
		elif mp > c[i][1]:
			mplist.append(c[y][1])

totalmp = 0
for i in range(10):
	totalmp += mplist[i]*youso[i]

print(totalmp)

Submission status: Wrong Answer

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