dkxm99   1년 전

뭐때문에 시간초과가 나는지 모르겠습니다...

보통 우선순위 큐로 다익스트라를 만들면 시간복잡도가 ElogV 인걸로 알고있는데 그래도 왜 시간초과가 나는지 궁금합니다. 

djs100201   1년 전

먼저 삽입된 더 먼 경로의 정점은 탐색을 시작하지 않아야 합니다

dladydwo123   1년 전

입력 경로 중에

1 2 10

1 2 2 

와 같이 같은 경로지만 비용이 다른 경로가 존재합니다. 이 경우를 처리해주셔야 합니다

dkxm99   1년 전

아 당연히 저런경우가 예제엔 없겠지 했는데 이런 생각이 문제군요... 그냥 문제만 보고 풀다보니 이런일이 발생하네요 ㅋㅋ 답변주신분들 감사합니다

dkxm99   1년 전

다익스트라 함수 중간에 

if (dist[cur] < cost) continue; 

한줄 집어넣어서 가중치가 더 크면 그냥 넘어가도록 하니 잘 됩니다.

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