kyo20111   2년 전

벨만 포드 알고리즘을 이용해서 풀어 보았습니다.


반례를 도저히 찾지 못하겠어서 올립니다 ㅠㅠ..


rhs0266   2년 전

Gee의 조건이 만족되려면 음수사이클이 존재하고, 그 음수사이클 위의 임의의 점에서 도착 지점을 갈 수 있는 경로가 존재해야 하지 않을까요? 도착 지점에 바로 연결되는 간선이 없더라도 간접적으로 갈 수 있는 경우가 있지 않을 지 고민해보시면 좋을 것 같습니다.

kyo20111   2년 전

도착지점에 간접적으로 갈 수 있는 음수 사이클이 존재하면 갱신을 할때 도착 지점도 갱신되지 않을까 해서 넘겼습니다. 제가 잘못 생각하고 있는건가요?

kyo20111   2년 전



이런 경우에 문제가 되는군요 감사합니다.13c0d4e3-479d-4ad5-8e6c-7de525b380f0

fksk94   4달 전

위의 케이스

5 0 4 6
0 1 10000
1 2 0
2 1 0
1 3 0
0 3 0
3 4 0
0 0 1 0 0

답은 Gee입니다.

저도 오답나오네요. 감사합니다!

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