BaekJoon
[BaekJoon] 1865번 웜홀 (Java) 문제 풀이 [Gold 3]
문제 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 어떻게 풀 것인가? 문제를 잘 읽어보자. 웜홀에 들어가면 시간은 뒤로간다. 그말인 즉슨 현재 간선 간의 가중치가 시간이라는 점에서 웜홀의 간선은 음의 가중치를 갖는 것이다. 다시말하면 다익스트라 알고리즘으로는 풀 수가 없다. 그렇다면 문제에서 요구하는 것은 무엇일까? 바로 벨만 - 포드 알고리즘이다. 즉, 현재 문제가 원하는 것은 벨만 포드 알고리즘을 이용하여 음수 사이클이 발생..
