[백준] 골3 - 웜홀

1865번: 웜홀

문제 설명

• N개의 지점, M개의 도로, W개의 웜홀이 있다.
• N개의 지점에서 M개 만큼의 가중치 방향 간선이 존재한다.
• N개의 지점에서 W개 만큼의 음수가중치 방향 간선이 존재한다.
• 어느 특정 지점에서 음의 사이클이 있는지 확인하는 문제이다.

풀이

문제를 이해했다면 벨만포드 알고리즘을 사용해야 된다는게 자명하다.

• 음의 사이클 여부를 알기 위해 벨만포드 알고리즘을 사용한다.
• 음의 비용, 음의 사이클이 있는 경우에 벨만포드 알고리즘을 사용한다.
• 방향 그래프일때 벨만포드 알고리즘을 사용한다. (이건 기본)

코드