1865번 - 웜홀
출발점을 0 혹은 1로 잡은 코드가 많은데,
vertex 0 이 독립된 component 인 case를 생각해보면 항상 "NO"가 나올 수 밖에 없습니다.
아무튼 독립된 component인 경우를 생각해야 할거같습니다.
간단한 테스트 케이스 남깁니다.
14 2 12 3 33 4 44 2 8
negative cycle이 있기 때문에 "YES"가 나와야하는데, start point를 1번에서 시작하면 도달할 수 있는 다른 점이 없기 때문에 "NO"가 나오게 됩니다.
따라서 모든 start point에 대해서 bellman-ford 알고리즘을 적용하여 negative cycle이 있는지 체크해봐야 합니다.
https://www.acmicpc.net/source...
등등 많은 코드들이 0 혹은 1에서만 check 한거 같습니다.
문제의 조건을 추가했습니다.
댓글을 작성하려면 로그인해야 합니다.
progresivojs 6년 전 2
출발점을 0 혹은 1로 잡은 코드가 많은데,
vertex 0 이 독립된 component 인 case를 생각해보면 항상 "NO"가 나올 수 밖에 없습니다.
아무튼 독립된 component인 경우를 생각해야 할거같습니다.
간단한 테스트 케이스 남깁니다.
1
4 2 1
2 3 3
3 4 4
4 2 8
negative cycle이 있기 때문에 "YES"가 나와야하는데, start point를 1번에서 시작하면 도달할 수 있는 다른 점이 없기 때문에 "NO"가 나오게 됩니다.
따라서 모든 start point에 대해서 bellman-ford 알고리즘을 적용하여 negative cycle이 있는지 체크해봐야 합니다.
https://www.acmicpc.net/source...
https://www.acmicpc.net/source...
https://www.acmicpc.net/source...
https://www.acmicpc.net/source...
등등 많은 코드들이 0 혹은 1에서만 check 한거 같습니다.