BaekJoon 1956번 : 운동 (python)

BaekJoon 1956번 : 운동 (G4 37.945%)

해당 문제는 두 마을 즉, 두 개의 정점을 왕복할 수 있는 사이클을 찾고 그 사이클중에서의 최솟 값을 찾으라는 문제이다.

주어진 조건 중 정점 V와 간선 E의 범위를 보았을 때 V가 400이하 인 것을 보았을 때 플로이드 워셜 알고리즘의 시간복잡도인 O(N^3)에 들어가기 때문에 플로이드 워셜 알고리즘을 이용한 풀이가 가능할 것이라 생각했다.

• 플로이드 워셜 알고리즘을 통해 각 정점들끼리의 최단 경로를 모두 계산을 해놓는다.
• 계산된 리스트에서 a != b가 아닌 조건에서 a에서 b까지의 거리와 b에서 a까지의 거리의 합이 최소가 되는 값을 구한다.
• 만약 모든 사이클을 검색해서 저장된 사이클의 최소 합 result가 INF이상이라면 해당 사이클은 운동 경로를 찾지 못한 것으로 간주해서 예외처리로 -1을 출력한다.

# 최소 사이클 도로 길이의 합, 찾는 것이 불가능할 경우 -1
#플로이드 워셜 -> a,b와 b,a가 가장 작은 값들 구하기
import sys
input = sys.stdin.readline
INF = 1e10

N, M = map(int,input().split())
graph = [[INF]*(N+1) for _ in range(N+1)]

for i in range(1,N+1) :
    graph[i][i] = 0

for _ in range(M) :
    a,b,c = map(int,input().split())
    graph[a][b] = min(graph[a][b], c)

for k in range(1, N+1) :
    for a in range(1, N +1) :
        for b in range(1, N+1) :
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
result = INF
for a in range(1, N+1) :
    for b in range(1, N+1) :
        if a != b :
            result = min(result, graph[a][b] + graph[b][a])

if result >= INF :
    print(-1)
else :
    print(result)