https://www.acmicpc.net/problem/1865 이 문제는 양방향 도로와 단방향 웜홀(시간이 뒤로감) 이 주어지고 이 때 음의 사이클이 존재하는지 물어보는 문제이다. 음의 사이클이 있는지를 알아내려면 벨만-포드 알고리즘을 쓰는 것이 제격이다. 벨만 - 포드 알고리즘은 그래프의 노드의 개수만큼 반복하며, 다익스트라 알고리즘처럼 경유하는 경우가 더 짧을 경우 계속해서 갱신하는 방식이다. 얼핏보면 쓸데 없는 계산을 더하는 것처럼 보이지만, 이 알고리즘의 장점은 이미 그래프의 노드의 개수만큼 반복하여 최적의 거리를 구했다고 생각했을때, 한번 더 돌려서 이때 최적경로가 갱신된다면, 음의 사이클이 생긴 것이라는 것을 알아챌 수 있단 점이다. 필자는 본디 처음엔 거리 리스트를 math.in..