Jonyo Programming

[BOJ 3860(P5)리뷰] 시작점부터 시작하여 목적지까지 도착해야 한다. 묘지가 있는곳으로는 이동할 수 없으며, 귀신 구멍이라는 특정한 칸으로 이동하면 다른 곳으로 시간을 워프하여 이동할 수 있다. 이때 시간을 과거로 되돌릴 수 있다. 인접한 칸을 간선으로 갖고, 귀신 구멍이라는 특별한 간선을 갖는 그래프라고 생각하면 된다. 다만, 과거로 되돌아 갈 수 있다고 했으니 음의 가중치를 갖는 그래프이다. 문제에서 최단거리를 구하라 했으니 최단거리를 구하는 알고리즘을 사용해야 한다. 시작지와 목적지가 주어져 있으므로 다익스트라 알고리즘이 적합하겠지만, 간선에 음의 가중치가 붙을 수 있으므로 벨만포드 알고리즘을 사용해야 한다. 만약 음의 사이클이 존재하면 "Never"를, 음의 사이클은 존재하지 않지만 목적지..