문제

[백준] 궁금한 민호 (Gold 2)

요약

  • M개의 도시, N개의 도로
  • 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.
  • 도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.
  • 모든 쌍의 도시에 대해 최소 이동 시간이 주어지면, 존재할 수 있는 도로의 개수가 최솟값일 때, 모든 도로의 시간의 합을 구하라.
  • 불가능한 경우 -1을 출력한다.

분류

  • 플로이드 워셜

풀이

1. 내 풀이 (플로이드 워셜)

  • A에서 B를 거쳐 C로 가는 경로가 A에서 C로 가는 최단 경로라면, A-C 경로를 지울 수 있다. A-B 경로나 B-C 경로를 지우지 않는 이유는 다른 최단 경로가 이를 지나갈 수 있기 때문이다.
  • 만약 A-B-C 경로가 A-C 경로보다 시간이 적게 걸린다면 “모든 쌍의 도시에 대해 최소 이동 시간이 주어지면” 라는 조건을 충족하지 못하기 때문에 불가능한 경우가 된다.


import sys
input = sys.stdin.readline
INF = sys.maxsize
n = int(input())

arr = [
    list(map(int, input().split())) for _ in range(n)
]


for inter in range(n):
    for r in range(n):
        for c in range(n):
            if r == c or r == inter or c == inter or arr[r][inter] == INF or arr[inter][c] == INF or arr[r][c] == INF:
                continue
            elif arr[r][c] == arr[r][inter] + arr[inter][c]:
                arr[r][c] = arr[c][r] = INF
            elif arr[r][c] > arr[r][inter] + arr[inter][c]:
                print(-1)
                sys.exit(0)

acc = 0
for val in arr:
    for v in val:
        if v != INF:
            acc += v

print(acc // 2)