[백준] 11657번 - 타임머신 (벨만-포드 알고리즘)

☞ 이 문제에서는 음수 간선이 존재하며, 출력 내용에서의 "만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다." 를 보면 그래프에 음수 사이클이 존재하는 경우 -1을 출력하라는 말이라고 볼 수 있다. 따라서 음수간선이 존재하며 음수 사이클의 존재를 판단 할 수 있는 '벨만-포드 알고리즘'을 사용하면 된다. '벨만-포드 알고리즘'은 아래에 잘 설명이 되어있으니 참고해주세요. https://withseungryu.tistory.com/34 벨만-포드 알고리즘 (Bellman-Ford Algorithm) ☞ 그래프의 최단 경로를 알고 싶고, 그래프에 음수 간선이 있으며, 음수 사이클이 존재 할 때 다익스트라 알고리즘을 사용해 최단 경로..