Submission #1872886

---

Source Code Expand

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 Info

Judge Result