1219번 - 오민식의 고민
벨만 포드 알고리즘을 이용해서 풀어 보았습니다.
반례를 도저히 찾지 못하겠어서 올립니다 ㅠㅠ..
Gee의 조건이 만족되려면 음수사이클이 존재하고, 그 음수사이클 위의 임의의 점에서 도착 지점을 갈 수 있는 경로가 존재해야 하지 않을까요? 도착 지점에 바로 연결되는 간선이 없더라도 간접적으로 갈 수 있는 경우가 있지 않을 지 고민해보시면 좋을 것 같습니다.
도착지점에 간접적으로 갈 수 있는 음수 사이클이 존재하면 갱신을 할때 도착 지점도 갱신되지 않을까 해서 넘겼습니다. 제가 잘못 생각하고 있는건가요?
위의 케이스
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입니다.
저도 오답나오네요. 감사합니다!
위에 그림 사례... 찢었다 ㅠㅠㅠㅠㅠㅠ 감사합니다!!! 많이 배우네요
댓글을 작성하려면 로그인해야 합니다.
kyo20111 5년 전 4
벨만 포드 알고리즘을 이용해서 풀어 보았습니다.
반례를 도저히 찾지 못하겠어서 올립니다 ㅠㅠ..