[Python] BOJ 1507번. 궁금한 민호

작성일 | In |

1507번. 궁금한 민호

문제 링크

풀이 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 1507번. 궁금한 민호
N = int(input())
s1 = []
s2 = [[1]*N for i in range(N)]
result = 0

for i in range(N):
    s1.append(list(map(int, input().split())))


def func(result):
    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 s1[i][j] == s1[i][k]+s1[k][j]:
                    s2[i][j] = 0
                elif s1[i][j] > s1[i][k]+s1[k][j]:
                    result = -1
    return result


result = func(result)


if result != -1:
    for i in range(N):
        for j in range(i, N):
            if s2[i][j]:
                result += s1[i][j]
print(result)

비고

  • 플로이드 와샬 알고리즘