플로이드 워셜 연습 - 운동(백준 1956)

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

이 문제에서 찾아야 하는 최단경로는, 출발지로 돌아와야 하는 순환경로라는 점이 다른 최단거리 구하는 점과 다르다. 처음에는 뭔가 복잡하게 접근할 뻔했는데, 생각해보니 자기 자신으로 오는 거리를 처음에 0으로 초기화하지만 않으면 되는 것이었다.

보통 다른 최단경로문제를 풀 때는 자신에게로 오는 거리를 처음부터 0으로 초기화해서 애초에 다른 아이를 경유하는 경우는 고려도 하지 않았다. 하지만 다른 노드에 대해서와 마찬가지로 INF(매우 큰 수)로 초기화해두면, 다른 노드로 갈 때 경유지를 고려하는 것과 마찬가지의 작업이 자기 자신에 대해서도 일어날 수 있다.

+ 지금 플로이드 워셜을 공부하던 터라 이 문제를 플로이드 워셜로 풀었지만, 다른 방식으로 좀 더 짧은 시간안에 풀 수는 없을까 하는 궁금함이 있다.

import sys

V, E = map(int, sys.stdin.readline().split())
INF = int(1e8)

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

# 최단거리를 갱신해갈 2차원 배열
for _ in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u][v] = w

# 경유지 고려하며 최단거리 갱신하기
for k in range(1, V+1):
    for i in range(1, V+1):
        for j in range(1, V+1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

answer = INF
# 자신에게로 향하는 거리들 구해보고 그 중 최소인 것으로 answer 갱신
for i in range(1, len(graph)):
    if graph[i][i] == INF:
        continue
    answer = min(answer, graph[i][i])

# 정답 제출 / 자신에게로 오는 게 모두 불가능했다면 -1리턴
if answer == INF:
    print(-1)
else:
    print(answer)