[Algorithm Problem] 운동 (BAEKJOON: 1956번)

Exercise Route (운동)

이 문제는 Floyd-Warshall 알고리즘을 이용해 모든 노드를 확인하여 자기 자리로 다시 돌아오는 간선의 최소값을 확인하는 문제입니다. 주의할 점은 $a \rarr b$로 가는 경로는 그 역이 성립하지 않는다는 것입니다.

보통 Floyd-Warshall Algorithm은 행렬의 $(i, i)$ 성분인 대각 성분들을 모두 0값으로 초기화합니다. 그리고 이 값이 음수로 최적화되면 음의 사이클이 존재한다고 결정합니다. 이를 경로에서 발생할 수 있는 최대값이나 시스템상의 최대값으로 초기화하면 0이 아닌 경로의 양수 최소값을 구할 수 있습니다. 이것이 문제 해결의 핵심 아이디어입니다.

소스코드

if __name__=="__main__":
    V, E = map(int, input().split(' '))

    node_matrix = [[float('inf') for i in range(V + 1)] for j in range(V + 1)]

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

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

    result = float('inf')
    for i in range(1, V+1):
        result = min(result, node_matrix[i][i])

    if result == float('inf'):
        print(-1)
    else:
        print(result)