juhongkim2   2년 전

문제에서 입력받는대로 그래프를 만들고 벨만포드 알고리즘을 사용해서

dist[0]<0이면 possible을 출력하도록 했습니다

그런데 50퍼센트에서 틀리더군요...


제 생각으로는 벨만포드를 사용했을때(0에서 출발)

dist[0]<0이 되었다면 문제의 possible조건을 (무조건)만족 한다고 생각했습니다

왜냐하면 최단거리를 구하는 알고리즘이니까 0으로 다시 돌아오지 않는다면 dist[0]는 항상 0이 되어야 하니까 말이죠...

(다시 돌아오더라도 음수사이클이 형성되지 않으면 dist[0]는 0이 될테니까...)


이 풀이방법에 어떤 부분이 잘못된건가요?

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