previc1   4년 전

벨만포드로는 통과했는데, SPFA로 풀어보니 82%에서 D값 계산하는 두번째 while문에서 무한루프에 빠지는 것같은데.. 

도저히 어떤 케이스인지 알기가 힘드네요.

혹시 반례 될만한게 있을까요?


chw0501   4년 전

혹시 이 문제 왜 그런지 반례 찾으셨나요??

저도 spfa로 풀면 똑같이 82퍼센트에서 시간초과 나는데 뭘해도 계속 시간 초과 나요ㅜㅜ

spfa로 풀면 완화하는 조건이 빠지는 경우도 있나요?


chw0501   4년 전

53번째 줄에 nxt에서 n으로 가는 경로가 있는 경우에만 완화를 해준다로 if문 조건 (cycle[nxt]&&) 을 추가하면

통과되네요

그런데 벨만 포드로 그냥 풀었을때는 완화조건을 그냥 거리가 더 짧아지는 것만 넣고 돌렸음에도

(if(D[nxt] < nxt_cost) )

 통과가 되는데

spfa로 풀면 왜 이 조건을 넣어야 하는지 아직 모르겠네요

혹시 이 글을 읽고 왜 그런지 아시는 분은 설명 부탁 드릴게요~

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