BOJ#1865 웜홀

BOJ#1865 웜홀

* 문제

https://www.acmicpc.net/problem/1865

* 풀이

벨만-포드 알고리즘을 활용하는 기본 문제입니다.

일단 기본적인 풀이 방법은 "BOJ#11657 타임머신" 문제와 같고,

음수 간선 사이클이 존재하는지 확인만 하면 되는 문제입니다.

주의할 점 #1)

도로에 방향이 없으므로,

도로 정보를 입력 받을 때 양방향으로 생각해야 한다는 점입니다.

 -> 결국 Edge의 개수는 2 * M + W

 -> 코드 상 여러번 쓰이게 되므로, 실수하지 않게 따로 변수로 저장해둡시다.

주의할 점 #2)

시작점이 주어지지 않았으므로, 시작점을 어느 곳으로 해야 할 지 결정해야 합니다.

음수 사이클은 웜홀이 연결된 지점에서만 존재 할 수 있으므로

웜홀의 목적지들을 배열에 따로 저장하여, 이것들을 벨만-포드 알고리즘의 시작점으로 넣어주었습니다.

 -> 출발점은 상관없음.

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%231865_Wormholes