알고리즘/백준
[백준] 1956 : 운동
bigkwangs
2024. 3. 18. 23:06
728x90
1956번: 운동
첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의
www.acmicpc.net
🤔 문제분석
사이클이 존재하면서 두 마을 사이의 거리중에서 가장 짧은 거리를 구하는 문제로 플로이드 워셜을 이용하여 문제를 해결한다. 플로이드 워셜은 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)
728x90