[백준] 1956번 - 운동 (파이썬)

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

# 운동
import sys
input = sys.stdin.readline
MAX = sys.maxsize
V, E = map(int, input().split())
arr = [[MAX for _ in range(V+1)] for _ in range(V+1)]
for _ in range(E):
    a, b, cost = map(int, input().split())
    arr[a][b] = cost

for k in range(1, V+1):
    for i in range(1, V+1):
        for j in range(1, V+1):
            if arr[i][j] > arr[i][k]+arr[k][j]:
                arr[i][j] = arr[i][k]+arr[k][j]

result = MAX
for i in range(1, V+1):
    result = min(result, arr[i][i])

if result == MAX:
    print('-1')
else:
    print(result)

 

플로이드와샬

1. 인접행렬로 입력을 받고 나머지는 MAX로 설정 (자기 자신 0으로 설정 X)

2. 플로이드 와샬 진행

3. 사이클일 경우를 찾아야하므로 i에서 시작해서 다시 i로 돌아올 경우만 min() 진행

4. result 출력

 

사이클이라는 단어에 집착해서 dfs로 풀려다가 실패하고 깔끔하게 플로이드와샬로 풀었다