백준 1507 궁금한 민호

gmlwlswldbs·2022년 1월 23일
0

코딩테스트

목록 보기
125/130
import copy
import sys
input = sys.stdin.readline
INF = int(1e9)

n = int(input())
g = [list(map(int, input().split())) for _ in range(n)]
# 1. deepcopy 해야하는 이유
tmp_g = copy.deepcopy(g)
# 아래 반복문에서 자기 자신으로 향하는 것들 모두 없어주기 위해
# 안 없애면 모든 간선이 갱신됨 (항상 자기 자신으로 가는 것은 0으로 최소라)
# for i in range(n):
#     g[i][i] = INF
ans = 0
for k in range(n):
    for i in range(n):
        for j in range(i+1, n):
            # 3. 왜 위의 조건이나 아래의 조건이 붙어야 하는지 (둘다 정답)
            if i == j or i == k or j == k:
                continue
            if g[i][j] == g[i][k] + g[k][j]:
                tmp_g[i][j] = INF
                tmp_g[j][i] = INF
            # 2. 갈 수 없는 경우는 갱신이 안된 경우가 아니라 
            # 주어진 것이 최단 거리가 아닐 때
            elif g[i][j] > g[i][k] + g[k][j]:
                ans = -1
if ans != -1:
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            if tmp_g[i][j] != INF:
                ans += tmp_g[i][j]
print(ans)

플로이드와샬을 반대로 생각해보는 문제 주석에 생각해 볼 것들 달았음

0개의 댓글