progresivojs   3년 전

출발점을 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 한거 같습니다.

startlink   3년 전

문제의 조건을 추가했습니다.

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