skydreamer21   4년 전

문제에서 주어진 테스트케이스 첫번째에서 뒤에 4개의 간선만 추가한 것입니다.

왜 반례인지 금방 찾으실 수 있을꺼에요, 그럼 해결책도 보일것이구요!

orct   3년 전

안녕하세요. 제가 잘못 생각하고 있는 건지 모르겠지만, 1 2 3 4 7로 갈 수 있는 경로가 있는게 아닌건가요?

얼핏 생각이 들었는데 5와 6을 충분히 돌면 7로 가서 1000을 뺏겨도 이득이니까, 계속 5와 6의 사이클을 돌게 되어서 최적의 경우가 나오지 않는다는 뜻인가요?

ryu_eclipse   1년 전

orct님, 이미 시간이 많이 흘러서 이해하셨을지도 모르겠습니다.

orct님이 말씀하신것처럼, 양수 사이클을 충분히 활용하게되면, -1000를 역전하는 순간이 옵니다. 이때문에 최적의 경우가 나오지 않습니다.


벨만포드코드에서 v-1번 반복문 실행 후, 최대 1000번(|w|가 최대 1000)을 추가로 더 돌려주면

양수사이클이 목적지까지의 거리에 영향을 주는지 판단할 수 있습니다.

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