1. 문제 설명

궁금한 민호

2. 문제 분석

플로이드-워셜 알고리즘은 k번 노드를 일종의 경유지로 사용, i번 노드에서 j번 노드까지 가는 경로를 단축시키는 알고리즘이다. 이때 이를 거꾸로 k번째 노드를 사용한 것을 비활성화할 수도 있다.

• 서로 다른 i, j, k번 노드를 사용할 때 nodes[i][j]와 nodes[i][k]+nodes[k][j] 값이 동일하다면 곧 k번을 경유지로 사용한 것이기 때문에 이를 비활성화할 수 있다.

3. 나의 풀이

import sys

n = int(sys.stdin.readline().rstrip())
nodes = []

for _ in range(n):
    nodes.append(list(map(int, sys.stdin.readline().rstrip().split())))

is_possible = True
deactivated = [[False for _ in range(n)] for _ in range(n+1)]
for k in range(n):
    for i in range(n):
        if i == k: continue
        for j in range(n):
            if j == k or i == j: continue

            # 서로 다른 i, j, k. i -> k -> j가 가능할 때
            if nodes[i][j] == nodes[i][k] + nodes[k][j]:
                deactivated[i][j] = True
                # k 사용한 경로를 막는다.
            elif nodes[i][j] > nodes[i][k] + nodes[k][j]:
                is_possible = False
                break
                # k 사용이 불가

if not is_possible: print(-1)
else:
    total = 0
    for i in range(n):
        for j in range(i, n):
            if not deactivated[i][j]: total += nodes[i][j]
    print(total)