[Python] BOJ 1956 - 운동

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

1956번: 운동

# 사이클 단어에 눈돌아가서 DFS로 풀려다 실패했다.

   단방향 그래프라서 그런건지, 그냥 플로이드-와샬 알고리즘을 사용해서 풀면되는 간단한 문제이다.

 

# dist에 각 정점들 사이의 거리를 입력해주고 플로이드-와샬 알고리즘을 사용해

   모든 dist값들을 최단경로로 갱신해준다.

 

# ans에 inf값을 넣어주고 dist배열을 모두 확인하며 dist[i][j]와 dist[j][i]가 inf이 아니라면

   사이클이 있으므로 ans에 min(ans, dist[i][j] + dist[j][i])를 넣어준다.

   (i에서 j까지 가는 경로가 있고, j에서 i까지 가는 경로가 있다면 사이클이 있다는 뜻)

 

# 최종적으로 ans에 inf이 들어있다면 사이클이 없으므로 -1을 출력해주고

   아니면 ans를 출력해준다.

   (i에서 i로 가는 dist값은 0이므로 i와 j가 같을때는 continue로 걸러주었다.)

 

import sys, math
input = sys.stdin.readline
V, E = map(int,input().split())
dist = [[math.inf] * (V+1) for _ in range(V+1)]
for _ in range(E):
    a, b, c = map(int,input().split())
    dist[a][b] = c
for i in range(1, V+1):
    dist[i][i] = 0

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

ans = math.inf
for i in range(1, V+1):
    for j in range(1, V+1):
        if i == j:
            continue
        if dist[i][j] != math.inf and dist[j][i] != math.inf:
            ans = min(ans, dist[i][j] + dist[j][i])

if ans == math.inf:
    print(-1)
else:
    print(ans)

(solved.ac 티어: 골드 4)

 

 

# 레이팅 1500을 찍음과 동시에 상위 100문제에 드디어 실버문제가 사라졌다!

   (언젠가 플레로 가득채우는 날이 오기를..)