플로이드 워셜로 구하는 그래프의 사이클의 길이

1956번: 운동

 

 

시작점에서 다시 시작점으로 돌아오는 사이클을 찾고자 하는데, 이때 길이 합이 가장 작은 사이클을 찾는 문제

 

사이클을 찾아야하나? 

 

dfs로 돌려서 사이클 찾고 해야하나.. 생각했는데

 

꼭짓점이 최대 400개이기도 하고 플로이드 워셜로 i번에서 시작해서 i번으로 돌아오는 최단 거리 dp[i][i]를 구하면 될것 같다

 

사이클이라는게 결국 i번에서 시작해서 i번으로 돌아오는거니까

 

일반적인 경우와 다르게 dp[i][i] = 0으로 하지말고 dp[i][i] = INF로 초기화함

 

 

꼭짓점이 1~V번이니까 1번부터 V번 돌아야하는거 실수하지말고

 

마지막에 dp[i][i]돌아서 최솟값을 찾으면 그것이 길이가 최소인 사이클의 길이

 

answer = INF로 변화없으면 사이클이 없는거고

 

from sys import stdin

v,e = map(int,stdin.readline().split())

INF = 10**18

dp = [[INF]*(v+1) for _ in range(v+1)]

for _ in range(e):
    
    a,b,c = map(int,stdin.readline().split())
    dp[a][b] = c

for k in range(1,v+1):
    
    for i in range(1,v+1):
        
        for j in range(1,v+1):
            
            dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j])

answer = INF

for i in range(1,v+1):
    
    if answer > dp[i][i]:
        
        answer = dp[i][i]

if answer == INF:
    
    print(-1)

else:
    
    print(answer)