Problem:


Score : 400 points

Problem Statement

Joisino the magical girl has decided to turn every single digit that exists on this world into 1.

Rewriting a digit i with j (0≤i,j≤9) costs c_{i,j} MP (Magic Points).

She is now standing before a wall. The wall is divided into HW squares in H rows and W columns, and at least one square contains a digit between 0 and 9 (inclusive).

You are given A_{i,j} that describes the square at the i-th row from the top and j-th column from the left, as follows:

If A_{i,j}≠-1, the square contains a digit A_{i,j}.

If A_{i,j}=-1, the square does not contain a digit.

Find the minimum total amount of MP required to turn every digit on this wall into 1 in the end.

Constraints

1≤H,W≤200

1≤c_{i,j}≤10^3 (i≠j)

c_{i,j}=0 (i=j)

-1≤A_{i,j}≤9

All input values are integers.

There is at least one digit on the wall.

Input

Input is given from Standard Input in the following format:

H W
c_{0,0} ... c_{0,9}
:
c_{9,0} ... c_{9,9}
A_{1,1} ... A_{1,W}
:
A_{H,1} ... A_{H,W}

Output

Print the minimum total amount of MP required to turn every digit on the wall into 1 in the end.

Sample Input 1

2 4
0 9 9 9 9 9 9 9 9 9
9 0 9 9 9 9 9 9 9 9
9 9 0 9 9 9 9 9 9 9
9 9 9 0 9 9 9 9 9 9
9 9 9 9 0 9 9 9 9 2
9 9 9 9 9 0 9 9 9 9
9 9 9 9 9 9 0 9 9 9
9 9 9 9 9 9 9 0 9 9
9 9 9 9 2 9 9 9 0 9
9 2 9 9 9 9 9 9 9 0
-1 -1 -1 -1
8 1 1 8

Sample Output 1

12

To turn a single 8 into 1, it is optimal to first turn 8 into 4, then turn 4 into 9, and finally turn 9 into 1, costing 6 MP.

The wall contains two 8s, so the minimum total MP required is 6×2=12.

Sample Input 2

5 5
0 999 999 999 999 999 999 999 999 999
999 0 999 999 999 999 999 999 999 999
999 999 0 999 999 999 999 999 999 999
999 999 999 0 999 999 999 999 999 999
999 999 999 999 0 999 999 999 999 999
999 999 999 999 999 0 999 999 999 999
999 999 999 999 999 999 0 999 999 999
999 999 999 999 999 999 999 0 999 999
999 999 999 999 999 999 999 999 0 999
999 999 999 999 999 999 999 999 999 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Sample Output 2

0

Note that she may not need to change any digit.

Sample Input 3

3 5
0 4 3 6 2 7 2 5 3 3
4 0 5 3 7 5 3 7 2 7
5 7 0 7 2 9 3 2 9 1
3 6 2 0 2 4 6 4 2 3
3 5 7 4 0 6 9 7 6 7
9 8 5 2 2 0 4 7 6 5
5 4 6 3 2 3 0 5 4 3
3 6 2 3 4 2 4 0 8 9
4 6 5 4 3 5 3 2 0 8
2 1 3 4 5 7 8 6 4 0
3 5 2 6 1
2 5 3 2 1
6 9 2 5 6

Sample Output 3

47



Sample input:
2 4
0 9 9 9 9 9 9 9 9 9
9 0 9 9 9 9 9 9 9 9
9 9 0 9 9 9 9 9 9 9
9 9 9 0 9 9 9 9 9 9
9 9 9 9 0 9 9 9 9 2
9 9 9 9 9 0 9 9 9 9
9 9 9 9 9 9 0 9 9 9
9 9 9 9 9 9 9 0 9 9
9 9 9 9 2 9 9 9 0 9
9 2 9 9 9 9 9 9 9 0
-1 -1 -1 -1
8 1 1 8


Sample output:
12

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))


H, W = inpl()

cost = [inpl() for _ in range(10)]

in_set = {1}
to_cost = [10**3 for i in range(10)]
to_cost[1] = 0
for _ in range(1, 10):
    bridge = {}
    for i in in_set:
        tmp_cost = 10 ** 4
        for j in range(10):
            if j in in_set or i == j:
                continue
            if cost[j][i] < tmp_cost:
                tmp_cost = cost[j][i]
                tmp_comer = j
        bridge[(i, tmp_comer)] = to_cost[i] + tmp_cost
    tt = min(bridge, key=bridge.get)
    to_cost[tt[1]] = bridge[tt]
    # print(tt, in_set, bridge)
    in_set.add(tt[1])

# print(to_cost)


ans = 0
for _ in range(H):
    ans += sum(to_cost[i] for i in inpl() if i != -1)
print(ans)

Submission status: Accepted

Solution code:
import heapq


class dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.visited = [-1 for i in range(len(adj))]
        self.heap = []

    def allSearch(self, _start):
        # スタート地点を設定
        heapq.heappush(self.heap, [0, _start])
        # ダイクストラ法でスタート地点からの距離を算出
        while 1:
            if len(self.heap) == 0:
                break
            start = heapq.heappop(self.heap)
            # 同じノードへ複数候補がある場合がある、一度訪れたノードへの候補は削除する
            if self.visited[start[1]] != -1:
                continue
            # 確定した距離をvisitテーブルに保持
            self.visited[start[1]] = start[0]
            for i in range(len(self.adj)):
                if self.visited[i] == -1 and self.adj[start[1]][i] != 0:
                    heapq.heappush(self.heap, [self.adj[start[1]][i] + self.visited[start[1]], i])
        # print("start:{} score:{}".format(_start, max(self.visited)))
        return self.visited


def func(h, w, c, a):
    cost = [0 for _ in range(10)]
    for i in range(len(c)):
        dij = dijkstra(adj=c)
        cost[i] = dij.allSearch(i)[1]
    # print(cost)
    totalCost = 0
    for i in range(len(a)):
        for j in range(len(a[0])):
            if a[i][j] >= 0:
                totalCost += cost[a[i][j]]
    return totalCost
h, w = [int(i) for i in input().split()]
c = [[0 for _ in range(10)] for _ in range(10)]
a = [[0 for _ in range(w)] for _ in range(h)]
for i in range(10):
    c[i] = [int(i) for i in input().split()]
for i in range(h):
    a[i] = [int(i) for i in input().split()]
print(func(h, w, c, a))
"""
print(func(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]]))
print(func(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]]))
print(func(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]]))
"""
# print("print(func({}, {}, {}, {}))".format(h, w, c, a))

Submission status: Accepted

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

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

c = [0]*10
for h in range(H):
    for w in range(W):
        if A[h][w] >= 0:
            c[A[h][w]] += 1

ans = 0
for i in range(10):
    ans += C[i][1]*c[i]

print(ans)

Submission status: Accepted

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

for x in range(10):
    for y in range(10):
        for z in range(10):
            c[y][z] = min(c[y][z], c[y][x] + c[x][z])

ans = 0
for x in range(h):
    for y in range(w):
        if a[x][y] >= 0:
            ans += c[a[x][y]][1]

print(ans)

Submission status: Accepted

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

from scipy.sparse.csgraph import floyd_warshall

H, W = map(int, input().split())
C = [None] * 10
for i in range(10):
    C[i] = list(map(int, input().split()))
field = [None] * H
for i in range(H):
    field[i] = list(map(int, input().split()))

# ちょうどよく隣接行列なので、そのままscipyのワーシャルフロイド使う
dist = floyd_warshall(C)

ans = 0
for i in range(H):
    for j in range(W):
        if field[i][j] != -1:
            # 該当マスの数字から1への距離を足していくだけ
            ans += dist[field[i][j]][1]
print(int(ans))

Submission status: Accepted

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

H, W = map(int, input().split())
C = [None] * 10
for i in range(10):
    C[i] = list(map(int, input().split()))
field = [None] * H
for i in range(H):
    field[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):
    for j in range(W):
        if field[i][j] != -1:
            # 該当マスの数字から1への距離を足していくだけ
            ans += C[field[i][j]][1]
print(ans)

Submission status: Accepted

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

from scipy.sparse.csgraph import dijkstra

H, W = map(int, input().split())
C = [None] * 10
for i in range(10):
    C[i] = list(map(int, input().split()))
field = [None] * H
for i in range(H):
    field[i] = list(map(int, input().split()))

# ちょうどデータの持ち方が隣接行列なので、そのままscipyのダイクストラ使ってみる
dist = dijkstra(C)

ans = 0
for i in range(H):
    for j in range(W):
        if field[i][j] != -1:
            # 該当マスの数字から1への距離を足していくだけ
            ans += dist[field[i][j]][1]
print(int(ans))

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
N=10
c=[[int(i) for i in input().split()] for i in range(N)]
A=[[int(i) for i in input().split()] for i in range(H)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if c[i][k]+c[k][j]<c[i][j]:
                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: Accepted

Solution code:
import heapq

H, W = [int(_) for _ in input().split()]
C = [[int(_) for _ in input().split()] for _ in range(10)]

Distance = [0] * 10

for p in range(10):
    q = p
    D = [float('inf')] * 10
    D[p] = 0
    HEAP = []
    d = 0
    c = 0
    while True:
        if p == 1:
            break
        for i in range(10):
            if D[i] == float('inf'):
                heapq.heappush(HEAP, (d + C[p][i], i))
        d, p = heapq.heappop(HEAP)
        D[p] = d
    Distance[q] = d
print(
    sum([
        sum([Distance[int(_)] for _ in input().split() if int(_) > -1])
        for _ in range(H)
    ]))

Submission status: Accepted

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

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

ans = 0
for row in G:
    for x in row:
        if x >= 0:
            ans += C[x][1]

print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd(graph):
    num_v = len(graph)
    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    return graph


h, w = map(int, input().split())
route = []

for i in range(10):
    S = list(map(int, input().split()))
    route.append(S)
graph = warshall_floyd(route)
result = 0
for i in range(h):
    A = list(map(int, input().split()))
    for a in A:
        if a != -1:
            result += graph[a][1]
print(result)

Submission status: Accepted

Solution code:
#D - Wall
H,W = [int(x) for x in input().split()]
C = [[0 for i in range(10)] for j in range(10)]
for i in range(10):
    C[i] = [int(x) for x in input().split()]
A = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    A[i] = [int(x) for x in input().split()]
#print(H,W) #
#print(C) #
#print(A) #
point = [C[i][1] for i in range(10)] #iを1に変換する魔力
way = [[i,1] for i in range(10)] #iを1に変換する方法
#print(point) #
#print(way) #

update = True
while update:
    update = False
    for i in range(10):
        for j in range(10):
            if i==j: continue
            #print(i,j,C[i][j],point[i]) #
            if  C[i][j]+point[j]<point[i]:
                #print(i,j, point, way) #
                point[i] = C[i][j] + point[j] 
                way[i].remove(way[i][-1])
                way[i] = [i]+way[j]
                update = True
                #print(i,j, point, way) #
    #print(point) #
    #print(way) #    
    #break
#print(point) #
#print(way) #
count = [0 for i in range(10)] #番号の数
for i in range(H):
    for j in range(W):
        if A[i][j]>=0: count[A[i][j]]+=1
#print(count) #
sum = 0
for i in range(10): sum += count[i]*point[i]
print(sum)

Submission status: Accepted

Solution code:
import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist

h, w = map(int, input().split())
adj = [[] for _ in range(10)]
for i in range(10):
    c = list(map(int, input().split()))
    for j in range(10):
        adj[i].append((c[j], j))
shortest = []
for i in range(10):
    shortest.append(dijkstra(adj, 10, i)[1])
ans = 0
for i in range(h):
    a = list(map(int, input().split()))
    for j in a:
        if j != -1:
            ans += shortest[j]
print(ans)

Submission status: Accepted

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

for i in range(10):#中間点
    for j in range(10):#起点
        if i == j:
            continue
        for k in range(10):#終点
            if i == k or j == k:
                continue
            tmp = c[j][i] + c[i][k]
            if c[j][k] > tmp:
                # print(j,i,k)
                c[j][k] = tmp

res = 0
for _ in range(H):
    for i in input().split():
        i = int(i)
        if i == -1:
            continue
        res += c[i][1]
print(res)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
dp=[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):
            dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k])
ans = 0
for i in range(h):
    a = list(map(int,input().split()))
    for j in a:
        if j >= 0:
            ans +=dp[j][1]
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
h,w = map(int, input().split())

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

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

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

Submission status: Accepted

Solution code:
import heapq

H,W = (int(i) for i in input().split())
C = []
for i in range(10):
    C.append( [int(j) for j in input().split()] )
SU = []
for i in range(H):
    SU += [int(j) for j in input().split()]

def Dijkstra(graph, start):
    N = 10
    d = {}
    prev = {}
    for i in range(N):
        prev[i] = None
        if i == start:
            d[i] = 0
        else:
            d[i] = float('inf')
    Q = []
    heapq.heappush(Q, (0, start))
    while Q:
        d_u, u = heapq.heappop(Q)
        if d[u] < d_u:#ダブりを回避
            continue
        for i in range(N):
            if graph[i][u]:
                temp = d_u + graph[i][u]
                if d[i] > temp:
                    d[i] = temp
                    prev[i] = u
                    heapq.heappush(Q, (d[i], i))
    return (d, prev)

def saitan(start, goal, d, prev):
    temp = goal
    res = [goal]
    while True:
        res.append(prev[temp])
        if prev[temp] == start:
            break
        else:
            temp = prev[temp]
    return res

d, prev = Dijkstra(C, 1)

res = 0
for i in SU:
    if i == -1:
        pass
    else:
        res += d[i]

print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from pprint import pprint
from collections import defaultdict
from scipy.sparse.csgraph import floyd_warshall
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)]

dist = floyd_warshall(c, directed=True)

A_cnt = defaultdict(int)
for h in range(H):
    for w in range(W):
        if A[h][w] != -1 and A[h][w] != 1:
            A_cnt[A[h][w]] += 1

ans = 0
for k,v in A_cnt.items():
    ans += dist[k][1] * v

print(int(ans))

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

h, w = map(int, input().split())
c = []
for i in range(10):#h:高さ
    c.append([int(m) for m in input().split()])
a = []
for i in range(h):#h:高さ
    a.append([int(m) for m in input().split()])
dist = []
for i in range(10):
    for j in range(10):
        dist.append([i, j, c[i][j]])

class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
# (src, dst, weight)
inputs = dist

g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)
    #g.add_edge(dst, src, weight)
spdi = {}
for i in range(10):
    d = Dijkstra(g, i)
    sp = format(d.shortest_distance(1))
    spdi[i] = int(sp)
#print('最短経路: {}'.format(d.shortest_path(1)))
#print('最短距離: {}'.format(d.shortest_distance(1)))

ncdi = {}
ncdi = defaultdict(int)
for i in range(h):
    for j in range(w):
        ncdi[a[i][j]] += 1
count = 0
for i in range(10):
    count += spdi[i] * ncdi[i]
print(count)

Submission status: Accepted

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

for k in range(10):
    for i in range(10):
        for j in range(10):
            ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j])
ans = 0
for row in A:
    for a in row:
        if a < 0: continue
        ans += ds[a][1]
print(ans)

Submission status: Accepted

Solution code:
from heapq import *
from collections import Counter
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)]
N = [0]*10
for i in range(H):
    CA = Counter(A[i])
    for j in range(10):
        N[j] += CA[j]
L = [(0,1)]
V = [-1]*10
while L:
    d, v = heappop(L)
    if not V[v] == -1:
        continue
    V[v] = d
    for i in range(10):
        if V[i] == -1:
            heappush(L, (d+C[i][v], i))
ans = 0
for i in range(10):
    ans += V[i]*N[i]
print(ans)

Submission status: Accepted

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

def w_f():
    cost=[]
    for i in range(10):
        cost.append(list(map(int,input().strip().split(' '))))

    for k in range(10):
        for i in range(10):
            for j in range(10):
                cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])
    return cost
    
d=w_f()
ans=0
for i in range(H):
    a=list(map(int,input().strip().split(' ')))
    for j in a:
        if j!=-1:
            ans+=d[j][1]
print(ans)

Submission status: Accepted

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

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

for k in range(10):
    for i in range(10):
        for j in range(10):
            cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])
ans=0
for i in range(H):
    a=list(map(int,input().strip().split(' ')))
    for j in a:
        if j!=-1:
            ans+=cost[j][1]
print(ans)

Submission status: Accepted

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

MinCost = [10000 for i in range(10)]
MinCost[1] = 0
Fin = [False for i in range(10)]
Fin[1] = True
Q = []
heapq.heappush(Q, (0, 1))
while Q:
    nowCost, nowNode = heapq.heappop(Q)
    Fin[nowNode] = True
    for i in range(10):
        if i != nowNode and Fin[i] == False:
            if MinCost[i] > nowCost + C[i][nowNode]:
                MinCost[i] = nowCost + C[i][nowNode]
                heapq.heappush(Q, (nowCost + C[i][nowNode], i))

Total = 0
for i in range(H):
    A = [int(i) for i in input().split()]
    for a in A:
        if a >= 0:
            Total += MinCost[a]
print(Total)

Submission status: Accepted

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

    minimum_cost = [float("inf")] * 10
    minimum_cost[1] = 0
    pattern = [{
        "via": 1,
        "cost": 0
    }]
    while len(pattern):
        p = pattern.pop(0)
        via = p["via"]
        cost = p["cost"]
        for i in range(10):
            nextcost = cost + c[i][via]
            if nextcost < minimum_cost[i]:
                minimum_cost[i] = nextcost
                pattern.append({"via": i, "cost": nextcost})

    retval = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == -1:
                continue
            retval += minimum_cost[A[i][j]]
    print(retval)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
c=[[int(i) for i in input().split()] for i in range(10)]
Points=[]
for i in range(0,10):
  if i==1:
    Points.append(0)
  else:
    Roots=[[i]]
    Roots_finished=[]
    for R in Roots:
      for j in range(10):
        if R[-1]==1:
          Roots_finished.append(R)
          break
        elif j in R:
          pass
        elif j==1:
          R_kari=list(R)
          R_kari.append(1)
          Roots.append(R_kari)
        elif c[R[-1]][j]<c[R[-1]][1]:
          R_kari=list(R)          
          R_kari.append(j)
          Roots.append(R_kari)
    S=1000000000000
    for r in Roots_finished:
      S_kari=0
      j=r[0]
      for i in r:
        S_kari+=c[j][i]
        j=i
      if S>S_kari:
        S=S_kari
    Points.append(S)
Magic_Power=0
for i in range(H):
  for j in input().split():
    if int(j)==-1:
      j=1
    Magic_Power+=Points[int(j)]
print(Magic_Power)

Submission status: Accepted

Solution code:
# time complexity: O(HW)
# space complexity: O(1)

import sys
fin = sys.stdin.readline
from copy import deepcopy


def warshall_floyd(w):
    num_vertices = len(w)
    dp = deepcopy(w)
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp


H, W = [int(elem) for elem in fin().split()]
c_list = [[int(elem) for elem in fin().split()] for _ in range(10)]
assert len(c_list[0]) == 10

A_list = [[int(elem) for elem in fin().split()] for _ in range(H)]
assert len(A_list[0]) == W

total_cost = 0
min_costs = warshall_floyd(c_list)
for A_row in A_list:
    for A in A_row:
        if A != -1 and A != 1:
            total_cost += min_costs[A][1]

print(total_cost)

Submission status: Accepted

Solution code:
import sys
fin = sys.stdin.readline
from copy import deepcopy


def warshall_floyd(w):
    num_vertices = len(w)
    dp = deepcopy(w)
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp


H, W = [int(elem) for elem in fin().split()]
c_list = [[int(elem) for elem in fin().split()] for _ in range(10)]
assert len(c_list[0]) == 10

A_list = [[int(elem) for elem in fin().split()] for _ in range(H)]
assert len(A_list[0]) == W

total_cost = 0
min_costs = warshall_floyd(c_list)
for A_row in A_list:
    for A in A_row:
        if A != -1 and A != 1:
            total_cost += min_costs[A][1]

print(total_cost)

Submission status: Accepted

Solution code:

import queue
from heapq import heappush, heappop

class Graph:

    INF = float('inf')
    
    def __init__(self,v_num,is_directed = False):
        self.is_directed = is_directed
        self.v_num = v_num
        self.E = []
        self.v_s_list = [[] for i in range(self.v_num)]
        
    def appendEdge(self,v1,v2,weight=1):
        if max(v1,v2,self.v_num-1)>=self.v_num or min(v1,v2)<0:
            print("ERROR: The vertex ID is wrong.")
            return False

        self.E.append([v1,v2,weight])
        
        if self.is_directed:
            self.v_s_list[v1].append([v2,weight])
        else:
            self.v_s_list[v1].append([v2,weight])
            self.v_s_list[v2].append([v1,weight])
        
        
    def BFS(self,v,usage="SSSP"):
        is_processed = [False for i in range(self.v_num)]
        distance_list = [Graph.INF for i in range(self.v_num)]
        Q = queue.Queue()
        Q.put(v)
        is_processed[v]=True
        distance_list[v] = 0
        while not Q.empty():
            v1 = Q.get()
            for v2 in self.v_s_list[v1]:
                if not is_processed[v2[0]]:
                    is_processed[v2[0]] = True
                    distance_list[v2[0]] = min(distance_list[v1]+1,distance_list[v2[0]])
                    Q.put(v2[0])
        if usage=="SSSP":
            return distance_list
        elif usage=="ConnectedComponent":
            cc_list = []
            for i in range(self.v_num):
                if is_processed[i]:
                    cc_list.append(i)
            return cc_list

    def getSSSPwithBFS(self,v):
        return self.BFS(v,"SSSP")
        
    def getConnectedComponent(self,v):
        return self.BFS(v,"ConnectedComponent")
        
    def getSSSPwithBellmanFord(self,v):
        distance_list = [Graph.INF for i in range(self.v_num)]
        distance_list[v] = 0
        pre_list = [None for i in range(self.v_num)]

        for i in range(self.v_num-1):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if distance_list[v2] > distance_list[v1] + d:
                    distance_list[v2] = distance_list[v1] + d
                    pre_list[v2] = v1
                    
        negative_loop_list = [False for i in range(self.v_num)]
        
        for i in range(self.v_num):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if d + distance_list[v1] < distance_list[v2]:
                    distance_list[v2] = d + distance_list[v1]
                    pre_list[v2] = v1
                    negative_loop_list[v2] = True
        
        return distance_list, pre_list, negative_loop_list

    def getSSSPwithDijkstra(self,v):
        distance_list = [Graph.INF for i in range(self.v_num)]
        distance_list[v] = 0
        pre_list = [None for i in range(self.v_num)]
        
        PQ = []
        for i in range(self.v_num):
            heappush(PQ,(distance_list[i],i))
        while len(PQ)>0:
            d,v1 = heappop(PQ)
            for v2 in self.v_s_list[v1]:
                if distance_list[v2[0]] > d + v2[1]:
                    distance_list[v2[0]] = d + v2[1]
                    pre_list[v2[0]] = v1
                    heappush(PQ,(distance_list[v2[0]],v2[0]))
        return distance_list,pre_list
    
H,W=list(map(int,input().split()))
C = []
for i in range(10):
    C.append(list(map(int,input().split())))

G = Graph(10,True)

for i in range(10):
    for j in range(10):
        if i!=j:
            G.appendEdge(i,j,C[i][j])

dto1 = []
for i in range(10):
    distance_list, pre_list, negative_loop_list=G.getSSSPwithBellmanFord(i)
    dto1.append(distance_list[1])
cost = 0
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        if A[j]!=-1:
            cost+=dto1[A[j]]
            
print(cost)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
p_min = []
for i in range(10):
    p = c[i]
    for j in range(10):
        pp = p
        for k in range(10):
            for l in range(10):
                pp[k] = min(pp[k], p[l] + c[l][k])
        p = pp
    p_min.append(p[1])
a = [list(map(int, input().split())) for _ in range(h)]
ans = 0
for i in range(10):
    count = 0
    for j in range(h):
        count += a[j].count(i)
    ans += count * p_min[i]
print(ans)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
import heapq
h,w = inpl()
edge = [] 
inf = float('inf')
for i in range(10):
    edge.append(inpl())
Q = [[inf for _ in range(10)] for _ in range(10)]

for i in range(10):
    decided = [False for _ in range(10)]
    H = []
    Q[i][i] = 0
    heapq.heappush(H,(0,i))
    for _ in range(10):
        while True:
            k = heapq.heappop(H)
            k = k[1]
            if not decided[k]:
                decided[k] = True
                break
        for j in range(10):
            if decided[j]:
                continue
            Q[i][j] = min(Q[i][k] + edge[k][j], Q[i][j])
            heapq.heappush(H,(Q[i][j],j))
ct = [0 for _ in range(11)]
for i in range(h):
    A = inpl()
    for j in range(w):
        ct[A[j]] += 1
ans = 0
for i in range(10):
    ans += ct[i]*Q[i][1]
print(ans)