[백준] 1956 : 운동

1956번: 운동

1956번: 운동

🤔 문제분석

사이클이 존재하면서 두 마을 사이의 거리중에서 가장 짧은 거리를 구하는 문제로 플로이드 워셜을 이용하여 문제를 해결한다. 플로이드 워셜은 i번째 마을에서 j번째 마을까지 최단경로를 구한다.

모든 i와 j에 대해서 (i번째 마을에서 j번째 마을까지 + j번째 마을에서 i번째 마을까지) 를 구하게 되면 가장 짧은 사이클을 구할 수 있다. 만약 i와 j가 연결되어있지 않다면 INF로 둔다.

💻 코드

import sys

V, E = map(int, input().split())
INF = sys.maxsize

edge = [[INF for _ in range(V+1)] for _ in range(V+1)]
distance = [[INF for _ in range(V+1)] for _ in range(V+1)]

for _ in range(E):
    a, b, c = map(int, input().split())
    edge[a][b] = c

for i in range(1, V+1):
    for j in range(1, V+1):
        if i == j:
            distance[i][j] = 0
        else:
            distance[i][j] = edge[i][j]

for k in range(1, V+1):
    for i in range(1, V+1):
        for j in range(1, V+1):
            if distance[i][k] + distance[k][j] < distance[i][j]:
                distance[i][j] = distance[i][k] + distance[k][j]

ans = INF
for i in range(1, V+1):
    for j in range(1, V+1):
        if i != j:
            ans = min(ans, distance[i][j] + distance[j][i])

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