[백준] 1956 운동 python(pypy)

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

1956번: 운동

처음 풀어보는 플로이드 와샬 문제이다.

플로이드 와샬을 몰랐기 때문에 다익스트라로 먼저 접근했다.

알고리즘 순서는 다음과 같다.

한 도시를 시작으로 다른 도시까지의 거리를 탐색한다. 모든 도시를 다 탐색해야하기때문에 반복문으로 돌리고 값을 받아온다.

한도시에서 다른 도시까지의 거리를 바탕으로 사이클을 탐색한다. 도시 사이 거리는 단방향이므로 양방을 모두 더해줘서 사이클을 만든다 (dist[i][j] + dist[j][i])

다 구한 값이 INF와 같거나 INF보다 큰경우 -1을 출력하고, 작은 경우 구한 값을 출력한다.

 

이렇게 진행했을때 pypy와 python 모두 시간초과가 되었다.

그래서 어쩔수 없이 플로이드 와샬을 찾아보고 해당 알고리즘으로 풀었다.

 

import sys; input = sys.stdin.readline
INF = 987654321

def floydWashall(linked_road):
    V = len(linked_road) - 1 

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


def main():
    # 0 입력
    V, E = map(int, input().split())
    linked_road = [[INF for _ in range(V + 1)] for _ in range(V + 1)]
    for _ in range(E):
        a, b, c = map(int, input().split())
        linked_road[a][b] = c
    for i in range(1, V + 1):
        linked_road[i][i] = 0
     
    # 1 모든 도시간 최소 거리 탐색
    floydWashall(linked_road)
    
    # 2 사이클 탐색
    answer = INF
    for i in range(1, V + 1):
        for j in range(i + 1, V + 1):
            answer = min(answer, linked_road[i][j] + linked_road[j][i])
    # 3 최소 도로 길이 출력
    if answer >= INF:
        answer = -1
    print(answer)

if __name__ == "__main__":
    main()