땃쥐네

문제 플랫폼 : 백준 번호 : 01865 제목 : 웜홀 난이도 : Gold 3 만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES, 불가능하면 NO를 출력 문제 : 링크 필요 지식, 해석 벨먼-포드 알고리즘 출발 정점에서 어떤 정점에 도착하기까지 기껏 많아봐야 N-1번의 간선을 순회하게 된다. 따라서 n-1번 모든 간선을 탐색하면서 이동비용을 최적화시키면 비용이 완전히 최적화된다. 그런데, 음의 사이클이 발생한다면 여기서 한 번 더 간선을 탐색했을 때 비용이 더 줄어드는 지점이 발생한다. 음의 가중치를 간선이 포함됐을 때 음의 사이클 발생여부 감지는 이 방식을 통해 수행하면 된다. 벨먼 포드 알고리즘의 시간복잡도는 O(NE)이다. 문제의 특수성 이 문제는 시작점이 주어지지 않았다. 각 지..