codemobi   4년 전

틀린 테스트 케이스를 도저히 못찾겠습니다. 문제 예제및 나름 몇가지 예제는 통과했는데, 제출만 하면 초기에 (아마1%?) 바로 틀렸다고 합니다. 고수님들 어디가 문제가 있는지 봐주세요.

ehddml3   4년 전

2 3

1
1 2 3
1 2 1
1 2 4

codemobi   4년 전

ehddml3 님,  틀린 테스트 케이스 감사합니다. 수정했습니다만 (81 line -> 82 line), 여전히 틀렸다고 나옵니다. 

어떤 부분이 틀렸는지 알 수 있을까요? 

ehddml3   4년 전

코드 이해하기가 힘들어서 여러저러 시도해 보았는데 잘 안되네요..ㅠ 확실한지는 모르겠으나..  priority queue 안에 직접 거리에 해당하는 값을 가지게해서 정렬한 후에 사용하거나, 지금 SPFA꼴을 쓰고 계신 것 같은데 그 모양을 유지하면서 priority queue 대신 그냥 queue를 써보는게 어떨지요ㄷ

https://en.wikipedia.org/wiki/...

codemobi   4년 전

기존 priority queue 에서 이미 queue 안에 있는 vertex 의 shortest path 값이 다시 더 짧은 거리로 변경되었을 때, priority queue 업데이트 처리가 미흡했는데, 이를 수정했더니 틀린것 대신 시간초과가 나와서 priority queue 자체는 insertion sort (?) 대신 heapsort 를 이용하여 O(logN) 으로 다시 구현했더니 성공했습니다. 다른 성공한 사람들 코드를 보니, 정말 간단히 구현하였네요. 감사합니다.

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