목록밸만포드 (1)

전자공학 및 알고리즘

백준 1865 - 웜홀(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 밸만포드 알고리즘을 이용해 푸는 문제입니다. 문제를 봤을 때, 다시 출발점으로 돌아왔을 때, 시간이 줄어들어 있으면(음의 값을 가지고 있다면) 되돌아 가면 됨으로 "YES" 아니면 "NO"를 출력하는 문제입니다. 해당 문제를 다익스트라 알고리즘을 이용해 풀 생각을 해봤지만, 웜홀을 통해 이동할 때는, 시간이 음의 값을 가집니다. 가중치가 음의 값을 가지고 있는 상황에..
백준 2022. 3. 6. 23:02
이전 Prev 1 Next 다음