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