[백준/플로이드와샬] 1956번 운동

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

1956번: 운동

 

[풀이 방법]

 

조건

1. 일방 통행 edge
2. 왕복하는 경우도 사이클로 포함

원하는 답

• 도로의 길이의 합이 가장 작은 사이클을 찾기

알고리즘 수업 들을 때, 교수님이 이건 그다지 좋지 않다고 했지만.. 생각하기는 편한 것 같다.

시작, 도착, 거치는 지점 모든 가능성을 다 해봐서

노드의 모든 연결점들의 길이를 구하는 것이다.

 

그리고 여기서는 사이클을 보기로 했으므로 [i][i] 중에서 최소 길이를 찾아서, 가장 작은 사이클을 구한다.

 

import sys

input = sys.stdin.readline
INF = sys.maxsize

V, E = map(int,input().split())
arr = [[INF] * V for _ in range(V)]

for _ in range(E):
    s,e,w= map(int,input().split())
    arr[s-1][e-1] = w

for k in range(V):#거침
    for i in range(V): #시작
        for j in range(V): #도착
            arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j])

ans = INF

for i in range(V):
    ans = min(ans,arr[i][i]) #본인으로 돌아오는 것중에 최소

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