1. 문제 설명

2. 문제 분석

플로이드-워셜 알고리즘의 nodes[i][j]는 곧 i번 노드에서 j번 노드로 향하는 최단 거리다. 이때 사이클은 i번에서 시작해 i번으로 도착하는 간선들의 집합인데, nodes[i][j]+nodes[j][i]는 i번에서 출발, j번까지 갔다가 i번 노드로 돌아오는 사이클인 셈이다. 플로이드-워셜을 통해 각 값이 최단 경로임이 보장되었기 때문에 최단 사이클 거리를 구할 수 있다.

• 두 노드 간의 거리가 INF가 아닐 때를 조건문으로 준 까닭은 오버플로우를 피하기 위해서다.

3. 나의 풀이

import sys

v, e = map(int, sys.stdin.readline().rstrip().split())
INF = sys.maxsize
nodes = [[INF for _ in range(v+1)] for _ in range(v+1)]
# for i in range(1, v+1): nodes[i][i] = 0
# 자기 자신을 향한 도로는 없기 때문에 거리 무한으로 설정
for _ in range(e):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    nodes[a][b] = c

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

local_min = INF

for i in range(1, v+1):
    for j in range(1, v+1):
        if nodes[i][j] != INF and nodes[j][i] != INF:
            # i -> j 갈 수 있고 j -> i 갈 수 있다면 i <-> j 사이클 거리는 합
            local_min = min(local_min, nodes[i][j] + nodes[j][i])

if local_min == INF: print(-1)
else: print(local_min)