반례입니다. 음수싸이클에 들어가면 도착지점에 도착할 수 없는 경우 반례가 되는 것 같습니다.

다만, 이 경우를 해결해도 답이 나오지 않을 수 있습니다.

@zlzmsrhak 님, 

해당 예제의 경우 음수싸이클이 생겨, Gee를 출력하도록 되어 있는데

혹시 다른 답이 나와야 하는 건지 궁금합니다.

벨만포드 알고리즘을 이용하였습니다. 

제가 문제를 이해한 바에 따르면, 

1. 도착지점에 무조건 도착을 해야 하고,

2. 그 시점에서 최대 이익을 얻는 것이 목표입니다.

2번 도시로 이동하게 되면 4번 도시에 절대 도착할 수 없기 때문에 무한대의 이익을 얻을 수 없고,

4번 도시에 도착하면 더 이동할 수 없어 이익이 10만큼 발생하는 것 같습니다.

예전 글이지만 저처럼 문제를 못풀어서 질문을 읽고있는 분들에게 알려드립니다. 

zlzmsrhak 님이 올려주신 반례

4 1 4 4 

1 2 0 

2 3 0

3 2 0 

1 4 10 

10 10 10 10

는 틀린 반례입니다.

문제를 읽어보시면 도시의 번호는 0~N-1번이라고 적혀 있습니다.

그러나 저 반례 자체는 좋은 반례라고 생각합니다.

올바른 반례는 다음과 같습니다.