반응형 벨만포드1 [백준 1865] 웜홀 문제 출처 : https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 웜홀은 시간이 거꾸로 가는 곳입니다. 따라서 최단 경로를 구할 때 음의 가중치를 가진 간선이라 생각하면 됩니다. 이 문제에서는 음의 사이클이 존재하는지 존재하지 않는지 확인하는 문제입니다. 벨만 포드 알고리즘을 사용하여 음의 사이클이 있다면 YES를, 음의 사이클이 없다면 NO를 출력하는 문제입니다. 다빈치코딩 알고리즘에 벨만포드 알고리즘을 설명해 놓았습니다. 벨만포드 .. 2023. 8. 30. 이전 1 다음 반응형