kyy627   3년 전

예제는 다 맞는데

제출하면 오답처리 됩니다.

어디가 잘못됬는지 알고 싶습니다.

zlzmsrhak   3년 전

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

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

kyy627   3년 전

@zlzmsrhak 님, 

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

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

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

zlzmsrhak   3년 전

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

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

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

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

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

ploffer11   1년 전

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

zlzmsrhak 님이 올려주신 반례

4 1 4 4 

1 2 0 

2 3 0

3 2 0 

1 4 10 

10 10 10 10

는 틀린 반례입니다.

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

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

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


댓글을 작성하려면 로그인해야 합니다.