✓

태그:

CLASS 4 ESSENTIAL

시작점 정해서 탐색했더니 시작점의 거리가 음수가 되었네…??

풀이 비스무리한거 보기

일반적인 도시와 도로의 그래프에 웜홀이 추가되었을 때, 사이클을 돌면 음수가 되는 경우가 있는지 찾는 문제입니다. 이 문제는 도로를 가중치가 양수인 양방향 간선, 웜홀은 가중치가 음수인 단방향 간선으로 생각할 수 있습니다. 이제 사이클을 돌았을 때 지나간 간선의 가중치의 합이 음수가 있는 경우를 찾아야 하는데, 이 때 사용하는 알고리즘이 벨만-포드 알고리즘입니다. 벨만-포드 알고리즘은 다익스트라보다 조금 느린 그래프 탐색 알고리즘이지만 음수 가중치를 넣어도 상관이 없으며, 한 사이클의 가중치 합이 음수인 경우도 자동으로 찾아줍니다. 이를 그대로 구현하면 문제를 풀 수 있습니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-01-03 15:10:21

---