[C++] 백준 1865 웜홀 [Gold3]
·
Baekjoon
https://www.acmicpc.net/problem/1865풀이 전략먼저 문제를 해석해보면 TC개의 Test case가 있고 각각의 Test case는 N개의 지점, M개의 양방향 도로, W개의 웜홀이 존재한다. 이 때 웜홀의 경우는 단방향 도로이고 웜홀을 통과하게 되면 시간이 거꾸로 흐르게 된다. 그렇기 때문에 음수 Cycle이 존재할 가능성이 존재하기 때문에 BellmanFord알고리즘을 이용하여야 한다. Dijkstra알고리즘의경우음수사이클을고려하지않는다.Dijkstra알고리즘의경우음수사이클을고려하지않는다.BellmanFord알고리즘을 이용하여 시간costcost을 구하고 만약 한 사이클을 돌았는데 cost의 총합이 음수인 경우 문제에서 구하고자 하는 “출발을 하였을 때보다 시간이 되돌아가 있는 경우”에 해당하기 때문에 YES를 출력하..