백준 1507 궁금한 민호
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)
플로이드와샬을 반대로 생각해보는 문제 주석에 생각해 볼 것들 달았음
Author And Source
이 문제에 관하여(백준 1507 궁금한 민호), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gmlwlswldbs/백준-1507-궁금한-민호저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)