저는 SPFA로 짰습니다. 벨만 포드는 뭐든 알고리즘 자체를 틀리신 분은 없다고 봅니다. 전형적인 음수 가중치 문제니까요.

답 선택에서 틀리시는 분들이 많으실 겁니다.

저는 다음과 같은 순위로 gg, gee, "%lld"를 구별하였습니다.

1) 일단 시작점에서 끝점으로 못간다면 gg후 return 0; ( 2)부터는 gg의 가능성이 0%입니다.)

2) 사이클이 생긴다면

         2-1) 해당 사이클에서 끝점으로 갈 수 있다면 gee

         2-2) 해당 사이클에서 끝점으로 못 간다면, 다른 지점에서는 열심히 끝점을 향해 가고 있는 것입니다.

                하지만 해당 사이클에서 끝점으로 가지 못 하는 것은 자명하기 때문에, 사이클을 끊어주어 더 이상 큐나 반복문이 돌지 않게 해줍니다.

3) 끝점까지 가지 못하는 사이클을 끊어 줌으로써 답 과정까지 나아갑니다. 사이클을 해제, 해제, 해제하다가 반복 루프가 끝이 나면 %lld를 출력합니다.

저는 답 선택에서 자꾸 헤맸네요...

시작점 바로 앞에서 루프가 10번, 20번 계속 돌고, 끝점까지의 과정은 한참 남은 경우 (끝점 최장거리는 업데이트가 아직 안 된상황)을 고려해 봅시다.