11657번 - 타임머신
제가 짠 코드는 다음과 같습니다.
#1에서 연결된 모든곳을 돌면서 dist[i] ( 출발지점에서 i까지 걸리는 거리)를 갱신해줍니다.
#2에서 한바퀴 더돌면서 dist2[i]를 만들어줍니다.
#3에서 출발지점을 제외한 dist를 확인하면서
두바퀴 돌았던(dist2[i]) 거리가 한번만 돌았던(dist[i])보다 작다면, 이는 negative cycle이 존재했다는 것입니다.
만약 모든 dist2[i]가 dist[i]보다 작다면, 전 구간이 negative cycle로 이루어지는 경우이므로
-1을 출력합니다.
다음과 같은 생각을 바탕으로 코딩하였는데 틀렸습니다.
어떤것이 문제일까요??
감사합니다.
38번째 줄에 i 시작값이 1이 아니라 0이 되어야하지 않을까요?
myungwoo
감사합니다. 주어진 그래프가 포레스트의 형식의 가능성을 생각하지 않았네요. 해결했습니다.
댓글을 작성하려면 로그인해야 합니다.
onlyhim 6년 전
제가 짠 코드는 다음과 같습니다.
#1에서 연결된 모든곳을 돌면서 dist[i] ( 출발지점에서 i까지 걸리는 거리)를 갱신해줍니다.
#2에서 한바퀴 더돌면서 dist2[i]를 만들어줍니다.
#3에서 출발지점을 제외한 dist를 확인하면서
두바퀴 돌았던(dist2[i]) 거리가 한번만 돌았던(dist[i])보다 작다면, 이는 negative cycle이 존재했다는 것입니다.
만약 모든 dist2[i]가 dist[i]보다 작다면, 전 구간이 negative cycle로 이루어지는 경우이므로
-1을 출력합니다.
다음과 같은 생각을 바탕으로 코딩하였는데 틀렸습니다.
어떤것이 문제일까요??
감사합니다.