algospot 시간여행(문제 ID: TIMETRIP) c++

알고스팟 문제 링크 : https://algospot.com/judge/problem/read/TIMETRIP

algospot.com :: TIMETRIP

V개의 은하가 있고 은하들은 웜홀로 연결되있다. 웜홀을 이용하면 시간이 미래(+) 또는 과거(-)로 이동한다.

지구(0번째 은하)에서 안드로메다(1번째 은하)까지 웜홀을 통해 간다고 했을때 최대 미래, 과거로 이동할때의 시간이 얼마나 바뀌는지 구하는 문제이다.

 

벨만-포드 알고리즘을 이용하면 음수간선을 포함한 그래프에 대해 각 정점간의 최단거리를 계산할 수 있다.

문제는 음수 사이클이 발견되었을때와 지구에서 안드로메다로 가는 경로가 없을때의 예외처리이다.

 

우선 음수 사이클이 발견되었을때 해당 음수사이클이 지구에서 안드로메다까지의 경로에 존재하냐를 판단한다.

경로상에 존재한다면 무한히 과거 혹은 미래로 갈 수 있기 때문에 INFINITY처리를 해준다.

만약 경로상에 존재하지 않는다면 무시하고 지구에서 안드로메다까지의 최단경로만 계산한 결과를 출력해주면 된다.

경로상에 존재하는지의 판단을 위해 플로이드 알고리즘을 이용하여 reachable[][]를 선행적으로 계산한다.

 

다음으로 지구에서 안드로메다로 가는 경로가 없을경우 UNREACHABLE처리를 해주어야 한다.

이 경우 bellman의 리턴값이 INF라고 생각하고 예외처리를 구현하면 실패할 수 있다.

지구에서 안드로메다까지의 경로는 없더라도 upper[target]이 완화되지 않고 계속 INF일 거란 보장은 없기 때문에 이 경우 역시 reachable[0][1]를 이용하여 처리한다.

 

 

 

코드 원본 : https://github.com/sbl133/JongmanBook/blob/main/30.%20ShortestPath/TIMETRIP.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2