1738번 - 골목길
벨만포드로는 통과했는데, SPFA로 풀어보니 82%에서 D값 계산하는 두번째 while문에서 무한루프에 빠지는 것같은데..
도저히 어떤 케이스인지 알기가 힘드네요.
혹시 반례 될만한게 있을까요?
혹시 이 문제 왜 그런지 반례 찾으셨나요??
저도 spfa로 풀면 똑같이 82퍼센트에서 시간초과 나는데 뭘해도 계속 시간 초과 나요ㅜㅜ
spfa로 풀면 완화하는 조건이 빠지는 경우도 있나요?
53번째 줄에 nxt에서 n으로 가는 경로가 있는 경우에만 완화를 해준다로 if문 조건 (cycle[nxt]&&) 을 추가하면
통과되네요
그런데 벨만 포드로 그냥 풀었을때는 완화조건을 그냥 거리가 더 짧아지는 것만 넣고 돌렸음에도
(if(D[nxt] < nxt_cost) )
통과가 되는데
spfa로 풀면 왜 이 조건을 넣어야 하는지 아직 모르겠네요
혹시 이 글을 읽고 왜 그런지 아시는 분은 설명 부탁 드릴게요~
댓글을 작성하려면 로그인해야 합니다.
previc1 4년 전
벨만포드로는 통과했는데, SPFA로 풀어보니 82%에서 D값 계산하는 두번째 while문에서 무한루프에 빠지는 것같은데..
도저히 어떤 케이스인지 알기가 힘드네요.
혹시 반례 될만한게 있을까요?