문제 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 solved.ac 난이도: Gold 4 다익스트라는 음수 사이클의 존재 여부를 알 수 없으므로 음수 사이클의 존재 여부를 판정할 수 있는 벨만-포드(Bellman-Ford) 최단 경로 알고리즘을 사용하자. 벨만-포드 알고리즘이 음수 사이클의 존재 여부를 알 수 있는 이유는 다음과 같다. 벨만-포드에서는 모든 정점에서 간선으로 연결된 정점으로 이동하는 거리의 완화를 시도한다...