[BOJ 1865] (벨만 포드) 웜홀 (C++)
웜홀 (Gold 3) 문제 전체 문제 보기 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 접근법 이번 문제는 음의 가중치가 주어지는 그래프에서 음의 사이클 여부를 파악하는 문제입니다. 간선에 가중치가 없는 그래프에서 최단 경로를 찾기 위해서는 BFS가 가장 효율적입니다. 만약 가중치가 존재한다면 다익스트라 알고리즘을 활용할 수 있습니다. 하지만 다익스트라 알고리즘은 반드시 모든 가중치는 양수가 보장되어야 한다는 단점이 있습니다. 음의 가중치를 가진 간선이 존재한다면 벨만 포드 알고리즘을 통해서 ..
