[백준] 1507번 - 궁금한 민호 (파이썬)

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

# 궁금한 민호

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

road = [[True]*N for _ in range(N)]

# 플로이드 와샬 역으로
result = 0
for k in range(N):
    for i in range(N):
        if i != k:
            for j in range(N):
                if i != j and k != j:
                    if arr[i][j] == arr[i][k]+arr[k][j]:
                        road[i][j] = False
                    elif arr[i][j] > arr[i][k]+arr[k][j]:
                        result = -1

if not result:
    for i in range(N):
        for j in range(i, N):
            if road[i][j]:
                result += arr[i][j]

print(result)

 

최단거리, 플로이드와샬
1. 입력을 받고, road 정의 ( i에서 j로 가는 도로가 있으면 True )
2. 플로이드와샬
    - i, j, k가 모두 다른 값이고 arr[i][j] == arr[i][k]+arr[k][j] 이면 다른 도시를 거쳐 왔다는 뜻 : 도로 False
    - i, j, k가 모두 다른 값이고 arr[i][j] > arr[i][k]+arr[k][j] 이면 최솟값이 아님 : result = -1
3. result가 0 그대로이면
    - 각 존재하는 도로의 가중치를 더해줌
4. result 출력

 

플로이드와샬을 반대로 하는 문제이다.

i, j, k가 같을 때도 진행을 하면 모두 0이 나온다.

자기 자신에서 자기 자신으로 가는 경우는 0이므로 당연히 모든 값이 0이 나온다.

따라서 i, j, k가 모두 다를 경우에만 진행해야 한다.