[python] 백준 1507 궁금한 민호

https://www.acmicpc.net/problem/1507

1507번: 궁금한 민호

 

문제 해결

플로이드-위셜 방법을 써야한다는 것은 쉽게 알 수 있었다.

하지만 어떻게 끊는 것을 구현할 지 생각이 나지 않았는데 check를 통해서 끊게 된다면 check[i][j]=0을 통해 이를 저장할 수 있었다.

 

CODE

import sys
input = sys.stdin.readline

def main():
    result = 0
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j or j == k or i == k: continue
                if board[i][j] == board[i][k] + board[k][j]:
                    check[i][j] = 0
                elif board[i][j] > board[i][k] + board[k][j]:
                    result = -1

    if result != -1:
        for i in range(n):
            for j in range(i+1, n):
                if check[i][j]:
                    result += board[i][j]

    print(result)


if __name__ == "__main__":
    n = int(input())
    board = [list(map(int, input().split())) for _ in range(n)]

    check = [[1 for _ in range(n)] for _ in range(n)]
    main()