벨만포드1 [C++] 백준 1865번: 웜홀 (벨만 포드) https://www.acmicpc.net/problem/1865문제 이해하기 문제의 요구사항은 다음과 같습니다.도로와 웜홀의 정보가 주어질 때, 줄어든 시간으로 출발 위치에 도착할 수 있는지 그 여부를 구하여라.시간복잡도 어림하기벨만 포드(Bellman Ford) 알고리즘 이번 문제에서 웜홀은 그 가중치만큼 시간을 줄이는 역할을 합니다. 즉, 음의 가중치를 가지는 간선입니다. 문제에서 줄어든 시간으로 출발 위치에 도착 가능한지를 물어보았습니다. 줄어든 시간으로 출발 위치에 도착 가능하다는 말은 음의 가중치로 인해 최단거리가 무한히 갱신된다는 것을 의미하고 이는 그래프에 음의 사이클이 존재한다는 것을 의미합니다. 그래프에 음의 사이클이 존재하는지 확인하는데 적합한 알고리즘은 벨만 포드 알고리즘입니다. 기.. 2024. 8. 20. 이전 1 다음