11657 타임머신

음수사이클을 검사해야하기 때문에 벨만포드 알고리즘을 사용해야 한다

벨만포드 알고리즘은 요약하면

1. 시작점에서의 모든 정점의 최단 거리를 구할 수 있다

2. 정점 간의 최단 거리는 최대 V-2개의 정점이 나올 수 있고, 이때 V-1개의 간선으로 이뤄져 있다

3. 모든 정점에 대해서 V-1개의 간선을 검사해야므로 시간복잡도는 O(VE)다

 

문제: https://www.acmicpc.net/problem/11657

https://github.com/surinoel/boj/blob/master/11657.cpp