[백준-파이썬] 1956: 운동

문제로 가기!

플로이드 워샬 문제인데, 사이클 부분을 판단하는 게 새로웠다.

사이클인지 판단하는 방법은 i에서 j로 가는 길이 있고, j에서 i로 가는 길이 있는지 봐주는 것이다.

같은 곳으로 가는 건 봐주면 안되므로 i==j인 경우는 continue했다.

처음에 INF를 401로 설정해서 틀렸다.
V는 400까지 있고, 거리는 10000까지이므로 401X 10000를 INF로 잡으니 맞았다.

'''
운동
https://www.acmicpc.net/problem/1956
'''

import sys

input = sys.stdin.readline
INF = 401 * 10000

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

for _ in range(E):
    start, end, dist = map(int, input().split())
    board[start][end] = dist  # 일방 통행 도로

for i in range(V + 1):  # 자기 자신으로 가는 경우 거리 0
    board[i][i] = 0

# 플로이드 워샬
for k in range(1, V + 1):
    for i in range(1, V + 1):
        for j in range(1, V + 1):
            board[i][j] = min(board[i][j], board[i][k] + board[k][j])

# 도로 길이 합이 가장 작은 사이클!
ans = INF
for i in range(1, V + 1):
    for j in range(1, V + 1):
        if i == j:  # 자기 자신으로 가는 경우는 continue
            continue
        else:
            # 사이클이 있으면
            if board[i][j] != INF and board[j][i] != INF:
                ans = min(ans, board[i][j] + board[j][i])

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