[백준 / BOJ] 1865 웜홀 (SPFA)

문제

출처 : www.acmicpc.net/problem/1865

1865번: 웜홀

백준이가 어느 지점에서 출발하여, 다시 시작지점으로 돌아왔을때, 출발하였을 시간보다 시간이 더 줄어들었는지 찾는문제이다. 

만약 가능하다면, YES

아니라면, NO를 출력하면된다.

(도로는 양방향이며, 시간을 되돌려주는 웜홀은 단방향이다)

풀이

음수가중치(워홀)가 존재하므로 벨만포드 혹은 SPFA로 풀어야한다.

문제 이해를 잘못하여 몇번 틀렸었다.

난 출발지점이 1이라고 생각하고 탐색을 했는데, 그럴경우,

반례 : 

1

5 3 1

1 2 1

2 3 1

3 4 1

5 5 1

의 경우 YES를 출력해야하는데 NO를 출력한다.

위 반례를 해석하면, 1~4번노드는 무한히 과거로 돌아갈수없으니 NO를 출력해야한다. 하지만, 5번을 출발지점으로 잡았을때는 무한히 과거로 돌아가므로 출력은 YES가 되어야한다.

 

출발지점을 1로두고 SPFA알고리즘을 한번돌리는 코드를

 

1. 출발지점을 1~N으로 두고 현재 정점이 방문하지 않은 정점이라면, 현재 정점을 기준으로 SPFA를 돌린다.

2. SPFA를 돌리면서 방문한 정점의 최솟값을 전부 업데이트해준다.

3. 만약 SPFA를 돌리는 과정에서 음수사이클이 존재한다면, YES를 출력하고 해당 테스트케이스를 종료한다.

 

로 바꿧더니 정답이 나왔다.

 

무한히 과거로 가는 음수사이클을 찾는방법은,

한 정점을 N번 초과로 방문했다면 음수사이클이 존재한다고 가정했다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1865%20%EC%9B%9C%ED%99%80/main.cpp

devxb/JJUNalgo