Submission #73318646

---

Source Code Expand

N, K = map(int, input().split())

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

INF = 10**18
R = [[INF] * N for _ in range(N)]
for i in range(N):
    R[i][i] = 0

while K > 0:
    if K & 1:
        next_R = [[INF] * N for _ in range(N)]
        for i in range(N):
            for k in range(N):
                r_ik = R[i][k]
                if r_ik == INF:
                    continue
                row_a = A[k]
                row_next = next_R[i]
                for j in range(N):
                    v = r_ik + row_a[j]
                    if v < row_next[j]:
                        row_next[j] = v
        R = next_R

    next_A = [[INF] * N for _ in range(N)]
    for i in range(N):
        for k in range(N):
            a_ik = A[i][k]
            if a_ik == INF:
                continue
            row_a = A[k]
            row_next = next_A[i]
            for j in range(N):
                v = a_ik + row_a[j]
                if v < row_next[j]:
                    row_next[j] = v
    A = next_A
    K >>= 1

for i in range(N):
    if R[i][i] == INF:
        print("-1") 
    else:
        print(R[i][i])

Submission Info

Judge Result