[백준]1956 운동(Python)

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

1956번: 운동

 

문제 접근

 

앞서 배운 플로이드-워셜 알고리즘을 이용해 모든 노드 간의 최단 경로를 이차원 배열에 저장한다.

그중 자기 자신으로 돌아오는 값 중 가장 작은 값이 최소 비용의 사이클이라고 할 수 있다. 

 

코드 

import sys

input = sys.stdin.readline
INF = sys.maxsize

V,E = map(int, input().split())

graph = [[INF] * (V+1) for _ in range(V+1)]

for _ in range(E):
    s, e, w = map(int, input().split())
    if graph[s][e] > w:
        graph[s][e] = w

# 플로이드-워셜 알고리즘 수행 코드 
for cross in range(1, V+1): # 거쳐가는(cross) 노드를 기준으로
        for s in range(1, V+1):
            for e in range(1, V+1):
                if graph[s][e] > graph[s][cross] + graph[cross][e]:
                    graph[s][e] = graph[s][cross] + graph[cross][e]

answer = INF
for i in range(1, V+1):
    answer = min(answer, graph[i][i])

# print(graph)
if answer == INF:
    print(-1)
else:
    print(answer)

 

문제 회고

 

플로이드-워셜 알고리즘은 All-to-All의 3중 반복문으로 구성되어 있어 비교적 이해가 쉽다. 

다른 알고리즘으로 접근하는 것을 추가로 알아봐야겠다.