onlyhim   6년 전

제가 짠 코드는 다음과 같습니다.

#1에서 연결된 모든곳을 돌면서 dist[i] ( 출발지점에서 i까지 걸리는 거리)를 갱신해줍니다.

#2에서 한바퀴 더돌면서 dist2[i]를 만들어줍니다.

#3에서 출발지점을 제외한 dist를 확인하면서

두바퀴 돌았던(dist2[i]) 거리가 한번만 돌았던(dist[i])보다 작다면, 이는 negative cycle이 존재했다는 것입니다.

만약 모든 dist2[i]가 dist[i]보다 작다면, 전 구간이 negative cycle로 이루어지는 경우이므로

-1을 출력합니다.


다음과 같은 생각을 바탕으로 코딩하였는데 틀렸습니다.

어떤것이 문제일까요??

감사합니다.

myungwoo   6년 전

38번째 줄에 i 시작값이 1이 아니라 0이 되어야하지 않을까요?

onlyhim   6년 전

myungwoo

그렇게 하면 출발도시(0)도 포함인데, 0은 출력에서 제외되니까 상관없을 것같아서 제외했는데, 출발도시의 거리도 포함일까요??

myungwoo   6년 전

그 부분도 불안하긴한데 이후 싸이클 체크를 위해 반복을 city번 더 해주어서 상관은 없을 것 같네요.

다른 부분에 오류가 있는데, 아래 데이터가 틀립니다:

onlyhim   6년 전

myungwoo 


감사합니다. 주어진 그래프가 포레스트의 형식의 가능성을 생각하지 않았네요. 해결했습니다.

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