cocobo123   2년 전

힙을 이용한 다익스트라를 구현했습니다.

70번 부터 다익스트라 알고리즘입니다.

제가 궁금한 점은 이전에 다익스트라를 적용한 문제에서 똑같이 힙을 이용하여 다익스트라를 구현하고  풀었을 땐 맞았습니다.

하지만 이번에는 계속 틀렸다고 나오네요.

문제가 될 것 같은 check 를 없애면 정답이 나옵니다.

여기서 궁금한게

힙을 이용했을 때 check 를 쓰지 않아도 맞는 이유가 궁금합니다. 

또 check를 썼을 때 왜 틀렸는지 잘 모르겠습니다.

u -> v 로 가는 경로가 여러개 있다고 한 들

check[u] = 1 이고 v는 아직 check 되지 않았기에 충분히 갱신될텐데

제가 어느부분을 놓치고 있는지 궁금합니다.

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