juhongkim2   4년 전

구글 뒤져보니 힙 다익스트라 쓸 때 정점체크배열을 쓰던데

이 문제 정점 체크배열을 쓰니 오답이 나오더군요.

원래 평소에도 힙 다익스트라 사용할때 정점체크배열을 사용하지 않기는 했었는데

힙 다익스트라 사용할 때 꼭 정점체크배열을 사용해야 하나요?

아니면 굳이 사용하지 않아도 되나요?


만약 꼭 사용해야한다면 이 문제에서 정점체크배열을 쓰면 오답이 나오는 이유가 뭘까요?

nisroeld99   4년 전

정점체크 배열을 쓰는 이유는 시간단축? 인데  (한번가면 dijkstra는 최단거리값이 확정되므로 굳이 갈필요없음) 

속도에는 크게 영향을 주진 않는거 같습니다.  


그리고 위의 문제에서 check쓰면 틀렸던 이유는 


같은 정점과 정점사이의 이동에서는 포장을하고가면 무조건 빠르기때문에 

이번에 pave를 하지 않고 다음에 pave해서 최단거리가 나오는 경우를 체크해주지 못합니다. 


그래서 check[NODE_CNT][PAVE_CNT] 로 체크해주시면 됩니다. 

nisroeld99   4년 전

저도 궁금해서 check배열 지우고 다시해보는데 속도에는 큰 유의미한 차이는 존재하지 않는거같네요 (100,96으로 4ms정도 차이) 

juhongkim2   4년 전

답변 감사합니다.

계속 궁금했었는데 덕분에 해결되었습니다.

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