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:
h, w = map(int, input().split())

ct = [0]*10

refer = []

for _ in range(10):
    st = list(map( int, input().split()))
    refer.append(st)

tab = []
for _ in range(h):
    st = list(map(int, input().split()))
    tab.append(st)

for i in range(h):
    for j in range(w):
        if tab[i][j] != -1:
            ct[ tab[i][j] ] += 1

cost = [999999999999999999999]*10

for i in range(10):
    for j in range(10):
        cost[i] = min(cost[i], min(refer[i][j] + cost[j], refer[i][j] + refer[j][1]) )

ans = 0

for i in range(10):
    ans += (cost[i]*ct[i])

print(ans)

Submission status: Wrong Answer

Solution code:
def get_input():
    while True:
        try:
            s = input()
            if s == "-1":
                break
            yield ''.join(s)
        except EOFError:
            break

def my_change(N):
    if N>0:
        return min([info_c[N][i] + info_c[i][j] + info_c[j][1] for i in range(10) for j in range(10)])
    else:
        return 0

if __name__ == '__main__':
    IN = list(get_input())
    info_c = [list(map(int, IN[i+1].split())) for i in range(10)]
    info_A = [list(map(int, IN[i+11].split())) for i in range(int((IN[0].split())[0])) ]
    
    temp = [list(map(my_change,info_A[i])) for i in range(len(info_A))]
    ans = 0
    for i in range(len(temp)):
        ans = sum(temp[i]) + ans 
    print(ans)

Submission status: Wrong Answer

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

mint = [0 for i in range(10)]

minVal = 1000


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

for i in range(10):
    if i == 1:
        continue
    minVal = C[i][1]
    searched = [i]
    search(i, 0, searched[:])
    mint[i] = minVal

ans = 0
for i in A:
    if i == -1:
        continue
    ans += mint[i]
print(ans)

Submission status: Wrong Answer

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

mint = [0 for i in range(10)]

minVal = 1000


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

for i in range(10):
    if i == 1:
        continue
    minVal = C[i][1]
    searched = [i]
    search(i, 0, searched[:])
    mint[i] = minVal

ans = 0
for i in A:
    if i == -1:
        continue
    ans += mint[i]
print(ans)

Submission status: Wrong Answer

Solution code:
def get_input():
    while True:
        try:
            s = input()
            if s == "-1":
                break
            yield ''.join(s)
        except EOFError:
            break

def my_change(N):
    if N>0:
        return min([info_c[N][i] + info_c[i][j] + info_c[j][k] + info_c[k][1] for i in range(10) for j in range(10) for k in range(10)])
    else:
        return 0

if __name__ == '__main__':
    IN = list(get_input())
    info_c = [list(map(int, IN[i+1].split())) for i in range(10)]
    info_A = [list(map(int, IN[i+11].split())) for i in range(int((IN[0].split())[0])) ]
    
    temp = [list(map(my_change,info_A[i])) for i in range(len(info_A))]
    ans = 0
    for i in range(len(temp)):
        ans = sum(temp[i]) + ans 
    print(ans)

Submission status: Wrong Answer

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

mint = [0 for i in range(10)]

minVal = 1000


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

for i in range(10):
    if i == 1:
        continue
    minVal = C[i][1]
    searched = [i]
    search(i, 0, searched[:])
    mint[i] = minVal

ans = 0
for i in A:
    if i == -1:
        continue
    ans += mint[i]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

H, W = map(int, sys.stdin.readline().strip().split())
#print(H, W)

c = {}
for j in range(10):
    vs = [int(x) for x in sys.stdin.readline().strip().split()]
    for i, v in enumerate(vs):
        c[(i, j)] = v

wc = dict((i, 0) for i in range(10))
for j in range(H):
    vs = [int(x) for x in sys.stdin.readline().strip().split()]
    for i in range(W):
        v = vs[i]
        if v >= 1:
            wc[v] += 1


def p(c):
    print("x    0    1    2    3    4    5    6    7    8    9")
    for j in range(10):
        print("%d" % j, " ".join(("%4d" % c[i, j]) for i in range(10)))

for a in range(10):
    for b in range(10):
        break
        if a == b:
            c[b, a] = 0
        elif a == 9 and b == 1:
            c[b, a] = 1
        elif a + 1 == b:
            c[b, a] = 1
        else:
            c[b, a] = 100

#p(c)

#print()

# opt
for optn in range(10):
    changed = False
    for a in range(10):
        for b in range(10):
            if a == b:
                continue
            r = c[b, a]
            rm = min(c[i, a] + c[b, i] for i in range(10) if i != a and i != b)
            if rm < r:
                c[b, a] = rm
                changed = True
    if changed == False:
        pass
        break

#print(optn)
#p(c)
#print(wc)

r = sum((c[1, i] * wc[i]) for i in range(10))
print(r)

Submission status: Wrong Answer

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

mint = [0 for i in range(10)]

minVal = 1000


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

for i in range(10):
    if i == 1:
        continue
    minVal = C[i][1]
    searched = [i]
    search(i, 0, searched[:])
    mint[i] = minVal

ans = 0
for i in A:
    if i == -1:
        continue
    ans += mint[i]
print(ans)

Submission status: Wrong Answer

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,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] - 1]
         
print(sum_power)

Submission status: Wrong Answer

Solution code:
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

w, h = read_line(int, int)

c = []
for _ in range(10):
    c.append(read_line(int, int, int, int, int, int, int, int, int, int))

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

cost = 0
for _ in range(w):
    for a in read_line(*([int] * h)):
        if a > 0:
            cost += c[a][1]

print(cost)

Submission status: Wrong Answer

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

mint = [0 for i in range(10)]

minVal = 1000


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

for i in range(10):
    if i == 1:
        continue
    minVal = C[i][1]
    searched = [i]
    search(i, 0, searched[:])
    mint[i] = minVal

ans = 0
for i in A:
    if i == -1:
        continue
    ans += mint[i]
print(ans)

Submission status: Wrong Answer

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

mint = [0 for i in range(10)]

minVal = 1000


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

for i in range(10):
    if i == 1:
        continue
    minVal = C[i][1]
    searched = [i]
    search(i, 0, searched)
    mint[i] = minVal

ans = 0
for i in A:
    if i == -1:
        continue
    ans += mint[i]
print(ans)

Submission status: Wrong Answer

Solution code:
#http://abc079.contest.atcoder.jp/
# -*- coding: utf-8 -*-

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

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

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





def min_cost(i,j,current,min_cost_current):
    if i == j: return current
    for index in range(10):
        if i == index: continue
        if current + mp[i][index] < min_cost_current:
            min_cost_current = min_cost(index,j,current+mp[i][index],min_cost_current)
    return min_cost_current


mp_min_cost =[]
for i in range(10):
    tmp = []
    for j in range(10):
        if i == j : continue

        min_cost_current = mp[i][j]
        if min_cost_current == sorted(mp[i])[1]:
            tmp.append(mp[i][j])
            continue

        # from i to j
        for index in range(10):
            if i == index: continue
            if mp[i][index] < min_cost_current:
                min_cost_current = min_cost(index,j,mp[i][index],min_cost_current)
        tmp.append(min_cost_current)
    mp_min_cost.append(tmp)

amount = 0
for i in wall:
    for j in i:
        if j == -1 or j == 1: continue
        amount += mp_min_cost[j][1]
print(amount)

Submission status: Wrong Answer

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

mint = [0 for i in range(10)]

minVal = 1000
searched = []


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

for i in range(10):
    if i == 1:
        continue
    minVal = C[i][1]
    searched = []
    search(i, 0)
    mint[i] = minVal

ans = 0
for i in A:
    if i == -1:
        continue
    ans += mint[i]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = [int(x) for x in raw_input().split()]
c = [[int(x) for x in raw_input().split()] for line in xrange(10)]
a = [[int(x) for x in raw_input().split()] for line in xrange(h)]
min_cost = [c[x][1] for x in xrange(10)]
for x in xrange(10):
    visited = [[False] * 10 for tmp in xrange(10)]
    minn = c[x][1]
    visited[x][1] = True
    que = deque()
    que.append((x, 0))
    while que:
        current_num, mp_cnt = que.popleft()
        for y in xrange(10):
            if x == y:
                continue
            if visited[current_num][y]:
                continue
            if c[current_num][y] + mp_cnt < minn:
                if y == 1:
                    min_cost[x] = min(c[current_num][y] + mp_cnt, min_cost[x])
                else:
                    visited[current_num][y] = True
                    que.append((y, c[current_num][y] + mp_cnt))
            else:
                continue
print min_cost
cost = 0
for line in xrange(h):
    for col in xrange(w):
        if a[line][col] in [-1, 1]:
            continue
        else:
            cost += min_cost[a[line][col]]
print cost

Submission status: Wrong Answer

Solution code:
import sys

H, W = map(int, sys.stdin.readline().strip().split())
#print(H, W)

c = {}
for j in range(10):
    vs = [int(x) for x in sys.stdin.readline().strip().split()]
    for i, v in enumerate(vs):
        c[(i, j)] = v

wc = dict((i, 0) for i in range(10))
for j in range(H):
    vs = [int(x) for x in sys.stdin.readline().strip().split()]
    for i in range(W):
        v = vs[i]
        if v >= 1:
            wc[v] += 1


def p(c):
    print("x    0    1    2    3    4    5    6    7    8    9")
    for j in range(10):
        print("%d" % j, " ".join(("%4d" % c[i, j]) for i in range(10)))

#p(c)

#print()

# opt
for optn in range(10):
    changed = False
    for a in range(10):
        for b in range(10):
            r = c[b, a]
            rm = min(c[i, a] + c[b, i] for i in range(10))
            if rm < r:
                c[b, a] = rm
                changed = True
    if changed == False:
        pass
        #break

#print(optn)
#p(c)
#print(wc)

r = sum((c[1, i] * wc[i]) for i in range(10))
print(r)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

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

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

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

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

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

print(res)

Submission status: Wrong Answer

Solution code:
import sys

H, W = map(int, sys.stdin.readline().strip().split())
#print(H, W)

c = {}
for j in range(10):
    vs = [int(x) for x in sys.stdin.readline().strip().split()]
    for i, v in enumerate(vs):
        c[(i, j)] = v

wc = dict((i, 0) for i in range(10))
for j in range(H):
    vs = [int(x) for x in sys.stdin.readline().strip().split()]
    for i in range(W):
        v = vs[i]
        if v >= 1:
            wc[v] += 1


def p(c):
    print("x    0    1    2    3    4    5    6    7    8    9")
    for j in range(10):
        print("%d" % j, " ".join(("%4d" % c[i, j]) for i in range(10)))

#p(c)

#print()

# opt
for optn in range(100):
    changed = False
    for a in range(10):
        for b in range(10):
            r = c[a, b]
            rm = min(c[a, i] + c[i, b] for i in range(10))
            if rm < r:
                c[a, b] = rm
                changed = True
    if changed == False:
        break

#print(optn)
#p(c)
#print(wc)

r = sum((c[1, i] * wc[i]) for i in range(10))
print(r)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

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

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

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

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

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

print(res)

Submission status: Wrong Answer

Solution code:
import copy
import sys
import numpy as np
import heapq
import time

from math import *
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

class warshall_floyd:
    def __init__(self):
        self.A = []

    def execute(self, adj_mat):
        self.A = copy.deepcopy(adj_mat)
        for k in range(len(self.A)):
            for i in range(len(self.A)):
                if self.A[i][k] < sys.maxint:
                    for j in range(len(self.A)):
                        if self.A[k][j] < sys.maxint:
                            self.A[i][j] = min(self.A[i][j], self.A[i][k] + self.A[k][j])


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W] = [int(input_raw[0]), int(input_raw[1])]
    dist_mat = [[0 for i in range(10)] for j in range(10)]
    for i in range(10):
        input_raw = read_func().strip().split()
        cost_list = (list(input_raw))
        for j in range(10):
            dist_mat[i][j] = int(cost_list[j])

    Warshall = warshall_floyd()
    Warshall.execute(dist_mat)

    score = 0;
    for i in range(H):
        input_raw = read_func().strip().split()
        raw_list = list(input_raw)
        for j in range(W):
            num = int(raw_list[j])
            if num > 0:
                score += Warshall.A[num][1]

    print score;

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

A = [[0]*W for i in range(H)]
for i in range(H):
    a = list(map(int, input().split()))
    for j in range(W):
        A[i][j] = a[j]

for i in range(10):
    for j in range(10):
        for k in range(10):
            if i != j:
                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 and A[i][j] != 1:
            ans += c[A[i][j]][1]
print(ans)

Submission status: Wrong Answer

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

A = [[0]*W for i in range(H)]
for i in range(H):
    a = list(map(int, input().split()))
    for j in range(W):
        A[i][j] = a[j]

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] != -1 and A[i][j] != 1:
            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 = []
for _ in range(H):
    A += list(map(int, input().split()))

ans = 0
for i in range(10):
    c[i][i] = 10
for i in range(2, 10):
    if i not in A:
        continue
    index = i
    while True:
        minv = min(c[index])
        ans += minv
        index = c[index].index(minv)
        if index == 1:
            ans *= A.count(index)
            break
print(ans)

Submission status: Wrong Answer

Solution code:
# python3
# utf-8

import itertools

rows_nr, cols_nr = (int(x) for x in input().split())
d1___d2___cost = []
for i in range(10):
    d1___d2___cost_i___j = [int(x) for x in input().split()]
    d1___d2___cost.append(d1___d2___cost_i___j)
r_c___value = []
for row in range(rows_nr):
    c___value = [int(x) for x in input().split()]
    r_c___value.append(c___value)

f = d1___d2___cost
for i, v, u in itertools.product(range(10), repeat=3):
    f[u][v] = min(f[u][v], f[u][i] + f[i][v])
ans = 0
for row in r_c___value:
    for value in row:
        if value == '-1':
            continue
        ans += f[value][1]
print(ans)

Submission status: Time Limit Exceeded

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

a=[[0]*w for _ in range(h)]
for i in range(h):
    a[i]=list(map(int, input().split()))


def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(10):
        for i in range(10):
            for j in range(10):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d


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

Submission status: Time Limit Exceeded

Solution code:
import heapq
H, W = map(int, input().split())
edges = [[] for _ in range(10)]
for i in range(10):
    e_list = list(map(int, input().split()))
    for j in range(10):
        if j == i:
            continue
        edges[i].append([j, e_list[j]])
A = []
for i in range(H):
    A.append(list(map(int, input().split())))

def dijkstra(edges, num_v, start):
    dist = [float('inf')] * num_v
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])

    while len(q) > 0:
        _, u = heapq.heappop(q)
        for edge in edges[u]:
            if dist[edge[0]] > dist[u] + edge[1]:
                dist[edge[0]] = dist[u] + edge[1]
                heapq.heappush(q, [dist[u] + edge[1], edge[0]])
    return dist
ans = 0
for a_line in A:
    for a in a_line:
        if a == -1 or a == 1:
            continue
        ans += dijkstra(edges, 10, a)[1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template
def dijkstra(s,n,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True

        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

H,W = inputlist()
cost = [0]*10
for i in range(10):
    cost[i] = inputlist()
A = [0]*H
for i in range(H):
    A[i] = inputlist()

ans = 0

for x in range(H):
    for y in range(W):
        if A[x][y] == -1:
            continue
        d = dijkstra(A[x][y],10,cost)
        ans += d[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(d,s):
    for k in range(10):
        for i in range(10):
            for j in range(10):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d[s][1]

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

d = [[10**4]*10 for i in range(10)] 
for i in range(10):
    a = list(map(int,input().split()))
    for j in range(10):
      d[i][j] = a[j]
for i in range(10):
    d[i][i] = 0
    
ans = 0
for _ in range(h):
  c = list(map(int,input().split()))
  for i in c:
    if i != 1 and i != -1:
      ans += warshall_floyd(d,i)
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

def func(num, goto, ignore):
    if num == goto:
        return 0
    res = []
    for i in range(10):
        if i in ignore:
            continue
        nignore  = deepcopy(ignore)
        nignore.append(i)
        #print(num, i, goto, nignore)
        plus = func(i, goto, nignore) if d[i][goto] == -1 else d[i][goto]
        #d[i][goto] = plus
        tmp = c[num][i] + plus
        res.append(tmp)
    return min(res)

h, w = MAP()
c = [LIST() for _ in range(10)]
a = [LIST() for _ in range(h)]
d = [[-1 for _ in range(10)] for _ in range(10)]
for i in range(10): #iから1に変更する最小コスト
    if i == 1:
        continue
    res = func(i, 1, [i])
    d[i][1] = min(c[i][1], res)
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == -1 or a[i][j] == 1:
            continue
        ans += d[a[i][j]][1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys

H, W = map(int, input().split())
a = [[] for i in range(10)]
for i in range(10):
	c = [int(j) for j in input().split()]
	for j in range(10):
		a[i].append([c[j], j])
ans = 0
for i in range(H):
	A = [int(j) for j in input().split()]
	for j in A:
		if j == -1:
			continue
		b = [[0, j]]
		c = [False] * 10
		d = [sys.maxsize] * 10
		d[j] = 0
		while len(b):
			e = heapq.heappop(b)
			c[e[1]] = True
			for k in a[e[1]]:
				if c[k[1]]:
					continue
				if d[e[1]] + k[0] < d[k[1]]:
					d[k[1]] = d[e[1]] + k[0]
					heapq.heappush(b, [d[k[1]], k[1]])
		ans += d[1]
print(ans)